Thread: Help With Recursion!!!!

  1. #1
    Unregistered
    Guest

    Help With Recursion!!!!

    Whats the result if N = 5? I dont understand recursion. Can you also show me the steps? Thanks in Advance!

    int Fibonacci(int N)
    {
    if ((N == 1) || (N == 2)) // base cases
    return(1);
    else // recursive cases
    return(Fibonacci(N - 1) + Fibonacci(N - 2));
    }

  2. #2
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    What a recursive function does is it calls itself a number of times (obviously). And, you usually put a decrementation or incrementaion or it will be a not ending loop. Then, each function (of the same) does what it has to do and then they all return their value to the root funciton. I know, confusing.

    --Garfield
    1978 Silver Anniversary Corvette

  3. #3
    left crog... back when? incognito's Avatar
    Join Date
    Oct 2001
    Posts
    1,427

    Let me guess

    You're using Sams Teach Yourself C++ in 21 days??? I had the same problem..................
    There are some real morons in this world please do not become one of them, do not become a victim of moronitis. PROGRAMMING IS THE FUTURE...THE FUTURE IS NOW!!!!!!!!!

    "...The only real game I thank in the world is baseball..." --Babe Ruth

    "Life is beautiful"-Don Corleone right before he died.

    "The expert on anything was once a beginner" -Baseball poster I own.


    Left cprog on 1-3-2005. Don't know when I am coming back. Thanks to those who helped me over the years.

  4. #4
    the Corvetter
    Join Date
    Sep 2001
    Posts
    1,584
    Yeah, ol' Sammy didn't explain it too well.
    1978 Silver Anniversary Corvette

  5. #5
    Registered User
    Join Date
    Aug 2001
    Posts
    47
    Think of recursive functions as boxes within boxes. Your function was as follows:

    Code:
    int Fibonacci(int N) 
    { 
             if ((N == 1) || (N == 2)) // base cases 
                      return 1; 
             else 
                      return(Fibonacci(N - 1) + Fibonacci(N - 2)); 
    }
    Now, let's say we do the following: "int x = Fibonacci(5);"
    What does x equal now?

    The best way to diagram program flow of a recursive function, I find, if as a tree:

    Code:
    
                                   Fibonacci(5)
                                   /           \
                                  /             \
                                 /               \
                      Fibonacci(4)                Fibonacci(3)
                     /            \                /          \
                    /              \              /            \
         Fibonacci(3)             Fibonacci(2)  Fibonacci(2)  Fibonacci(1)
            /       \                    |           |              |
    Fibonacci(2)     Fibonacci(1)        1           1              1
          |               |
          1               1
    In an outline form, that would be this:

    Code:
    Fibonacci(5) = Fibonacci(4) + Fibonacci(3)
             Fibonacci(4) = Fibonacci(3) + Fibonacci(2)
                       Fibonacci(3) = Fibonacci(2) + Fibonacci(1)
                                  Fibonacci(2) = 1
                                  Fibonacci(1) = 1
                       Fibonacci(2) = 1
              Fibonacci(3) = Fibonacci(2) + Fibonacci(1)
                       Fibonacci(2) = 1
                       Fibonacci(1) = 1

    Hopefully, this helps.
    Last edited by TerranFury; 12-16-2001 at 12:40 PM.

  6. #6
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    Perhaps a different example may help understanding recursion.

    Take the faculty function: n!.

    Let's calculate 3!, it is: 3 x 2 x 1 = 6.
    Let's calculate 5!, it is: 5 x 4 x 3 x 2 x 1 = 120.

    As you can see, in general we can calculate n! as:

    n! = n x (n-1) x (n - 2) .. x 2 x 1.

    In general we start with n and end with 1. So multiplying with 1 is always the final step. The steps between are multiplying with the numbers between n and 1.

    int fac (int n)
    {
    if (n == 1) /* final step is reached */
    return 1;
    else
    return n * fac (n-1);
    }

    Let's trace this function, it will look like this:

    fac (5)
    5 * fac (4)
    5 * 4 * fac (3)
    5 * 4 * 3 * fac (2)
    5 * 4 * 3 * fac (1)
    5 * 4 * 3 * 1
    = 120

  7. #7
    Registered User marCplusplus's Avatar
    Join Date
    Nov 2001
    Posts
    68
    Hey,

    I started Sams Teach Yourself C++ in 21 days...and I too encountered this problem.
    After thinking about that function for a few hours, I finally got it .....

    When I started chapter 7 ( pointers i think ), I found out that the book does not explain the advanced stuff well enough.

    Therefore, I stopped reading the book and now I am reading C++ Interactive Course. I found it excellent and even though I'm still in chapter 3, I can already do stuff with classes, arrays, structures, loops etc.

    This book keeps building on what you've just learnt. It starts immediately from OOP and builds on it. In this way, you'll never forget what you did back in chapter 1.

    I found the Sams book 'explains' a different topic every chapter. I only found the first 6 chapters useful

    C++ Interactive Course does have some mistakes, but in my opinion, it helps me look at my code and find errors before even compiling.

    Well, e-mail me for info about the book

    Marc
    No matter how much you know, you NEVER know enough.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 02:58 AM
  3. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  4. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  5. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM