Results 1 to 6 of 6

Math Help - Recursive Algorithm Help

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    21

    Recursive Algorithm Help

    Here is the problem:

    Suppose a sequence is defined recursively be setting a_1 = 2 and a_2 = 9 and, for n\geq2 , requiring that a_n = 2a_{n-1} + 3a_{n-2}.

    Give a recursive algorithm for computing a_n, where n is a positive integer.


    Using the initial conditions, I could calculate a_3 , a_4 , etc., but that is not what the problem is asking for. I thought recursive definitions were when you set n = 0, but that makes the equation work with negative numbers. So, here I am, confused beyond belief with algorithms
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2009
    Posts
    6
    int recursiveFunc(int n){
    if(n<1) return 0; //This shouldn't be
    if(n==1) return 2;
    if(n==2) return 9;

    return ((2*recursiveFunc(n-1)) + (3*recursiveFunc(n-2)));
    }


    int main(){
    int n;
    int result;

    n=100 //n is arbitrary

    result=recursiveFunc(n);
    }

    and and, for , requiring that .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    21
    Quote Originally Posted by mkahraman View Post
    int recursiveFunc(int n){
    if(n<1) return 0; //This shouldn't be
    if(n==1) return 2;
    if(n==2) return 9;

    return ((2*recursiveFunc(n-1)) + (3*recursiveFunc(n-2)));
    }


    int main(){
    int n;
    int result;

    n=100 //n is arbitrary

    result=recursiveFunc(n);
    }

    and and, for , requiring that .

    The language you used makes no sense to me
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    The program that has been posted is in the computer language C, but it is a very very bad way of calculating the function. For a very similar example, and explanation of why it is bad see

    Dr. Dobb's | The Case for D | June 15, 2009

    Your teacher probably really does want you to come up with a solution like this, as the exercise is probably to get you familiar with the concept of a recursive function. But functions like this should absolutely not be calculated using recursion.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    6
    I'm not saying this the best way and know this algorithm is very bad for computing given function.

    But this is the way how to solve given problem in recursive manner.

    The program i wrote is in C programming language. I didn't try if it compiles or not.

    But i am sure this is the answer.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,738
    Thanks
    643
    Hello, minkyboodle!

    Are you sure of the wording of the problem?


    A sequence is defined recursively by: . a_1 = 2,\;\; a_2 = 9, \;\; a_n \:=\:2a_{n-1} + 3a_{n-2}\;\;\text{ for  }n \geq 2

    Give a (?) recursive (?) algorithm for computing a_n, where n is a positive integer.

    By my understanding, they've already given us the recursive algorithm.
    . . What they want is a "closed form" for the n^{th} term.

    There is a procedure for determining the generating function for a linear recursion,
    . . but I will wait until I get some clarification.


    ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

    Well, okay . . . Here's the answer:

    . . . a_n \;=\;\frac{1}{12}\bigg[11(3^n) + 9(\text{-}1)^n\bigg]

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 23rd 2009, 10:22 AM
  2. Recursive Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 6th 2009, 01:55 AM
  3. Recursive Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2008, 10:56 PM
  4. Recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 6th 2008, 04:50 AM
  5. Recursive algorithm
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: May 21st 2007, 03:15 PM

Search Tags


/mathhelpforum @mathhelpforum