Recursions....please help

This is a discussion on Recursions....please help within the C++ Programming forums, part of the General Programming Boards category; // Fibonacci series using recursion // problem from Sams Publishing (example) // Just in case =Fibonacci series 1,1,2,3,5,8,13,21,34.... (each number ...

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

    Recursions....please help

    // Fibonacci series using recursion
    // problem from Sams Publishing (example)
    // Just in case =Fibonacci series 1,1,2,3,5,8,13,21,34.... (each number after
    //the second number is the sum of the two numbers before it
    /* in C++ "programming terms" the nth numbers is the sum */
    //of n-2 and n-1, as long as n>2
    #include <iostream>

    int fib (int n);

    int main()
    {

    int n, answer;
    std::cout << "Enter number to find: ";
    std::cin >> n;

    std::cout << "\n\n";

    answer = fib(n);

    std::cout << answer << " is the " << n;
    std::cout << "th Fibonacci number\n";
    return 0;
    }

    int fib (int n)
    {
    std::cout << "Processing fib(" << n << ")... ";

    if (n < 3 )
    {
    std::cout << "Return 1!\n";
    return (1);
    }
    else
    {
    std::cout << "Call fib(" << n-2 << ") ";
    std::cout << "and fib(" << n-1 << ").\n";
    return( fib(n-2) + fib(n-1));
    }
    }
    /*#########################################*/

    OUTPUT
    Enter number to find: 6

    //for the purpose of this explanation start
    // counting lines on the next line
    Processing fib(6)... Call fib(4) and fib(5).
    Processing fib(4)... Call fib(2) and fib(3).
    Processing fib(2)... Return 1!
    Processing fib(3)... Call fib(1) and fib(2).
    Processing fib(1)... Return 1!
    Processing fib(2)... Return 1!
    Processing fib(5)... Call fib(3) and fib(4).
    Processing fib(3)... Call fib(1) and fib(2).
    Processing fib(1)... Return 1!
    Processing fib(2)... Return 1!
    Processing fib(4)... Call fib(2) and fib(3).
    Processing fib(2)... Return 1!
    Processing fib(3)... Call fib(1) and fib(2).
    Processing fib(1)... Return 1!
    Processing fib(2)... Return 1!
    8 is the 6th Fibonacci number

    My question is this if it returns 1 on line 3 (of output) right in fib(2) why does it keep going to fib(3) on line 4? In other words I understand how the program got up to number 3 I don't know however why it keeps going to line 4, would anybody please care to explain this? Also are recursions used a lot in C++ programming?
    UPDATE
    After looking over the example I've come to a conclusion and please tell me if I wrong so I can understand this, fib(6) divides in to fib(5) and fib(4), which are started in line 2 and 7 respectably which are in turn divided until each each of the numbers return 1 respectably.
    Last edited by incognito; 11-15-2001 at 12:57 PM.
    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.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,687
    > why does it keep going to fib(3) on line 4?
    In order to print this
    ...Processing fib(2)... Return 1!
    The previous call level was
    Processing fib(4)... Call fib(2) and fib(3).

    Given
    return( fib(n-2) + fib(n-1));
    fib(n-2) (n is 4) gets you to the fib(2) case, but you still have a fib(n-1) to add to that (which gets you fib(3), and hence fib(1) )
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. what are RECURSIONS....???
    By ajayd in forum C Programming
    Replies: 4
    Last Post: 02-16-2008, 09:42 PM
  2. Recursions killing me
    By salvadoravi in forum C Programming
    Replies: 12
    Last Post: 01-29-2008, 03:48 AM
  3. Recursions
    By incognito in forum C++ Programming
    Replies: 3
    Last Post: 11-27-2001, 07:12 PM
  4. Replies: 3
    Last Post: 11-17-2001, 08:16 AM
  5. need help with recursion's base case...
    By matheo917 in forum C++ Programming
    Replies: 8
    Last Post: 11-10-2001, 01:40 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21