Thread: a simple recursion question

  1. #1
    tetra
    Guest

    a simple recursion question

    hi ims orry bout asking for code on other problem i was just so lost, bcause my suckie teacher tried to make us do it WITHOUT teaching us recursion. i tried reading the recursion tutorial on the site it cleared some issues up, but not all, ok this is the only problem with recursion i have,


    lets say this....


    fibonacci numbers 0, 1, 1,2,3,5,8,13,21.....etc

    it adds previous values to get the next value...

    now, the code for the recursion in my book says....

    unsigned long fibonacci (unsigned long){

    if ( n == 0 || n ==1) // i understand this , the base case

    return n; // i get this too.

    else

    return fibonacci (n - 1 ) + fibonacci ( n - 2 );

    }

    in line... return fibonacci (n - 1 ) + fibonacci ( n - 2 ); why wouldnt it add the two rpevious values to make the recursion? why subtract??

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    fibonacci(n) is the number you want, and it is the same as the sum of the two previous elements: fibonacci(n-1) and fibonacci(n-2)

    If n is 3:

    fibonacci(3)
    fibonacci(2) + fibonacci(1)

    Since 2 != 0 and 2 != 1, fibonacci will be called again for n=2, this is the recursion:

    (fibonacci(1) + fibonacci(0)) + fibonacci(1)

    Since you know the values for n=0 and n=1, it is now calcuable.

    (1 + 0) + 1
    2
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Microsoft. Who? MethodMan's Avatar
    Join Date
    Mar 2002
    Posts
    1,198
    Its best to do a call trace when doing something with recursion.

    Lets say you call fibionacci(4), according to your code:

    Code:
    fib(4 -1) + fib(4-2)
    = fib(3) + fib(2) [ now each of these call fib ]
    = (fib(3-1) + fib(3-2)) + (fib(2-1) + fib(2-2))
    =(fib(2) + fib(1)) + (fib(1) + fib(0))
    =(fib(2-1) + fib(2-2) ) 1 +  (1 + 0)
    =(fib(1) + fib(0) + 1) + (1)
    = 3
    If you have a call to fib(n) you always have the two cases for it f(n-1) and f(n-2).
    -MethodMan-

    Your Move:Life is a game, Play it; Life is a challenge, Meet it; Life is an opportunity, capture it.

    Homepage: http://www.freewebs.com/andy_moog/home.html

  4. #4
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946

    Re: a simple recursion question

    Originally posted by tetra
    hi ims orry bout asking for code on other problem i was just so lost, bcause my suckie teacher tried to make us do it WITHOUT teaching us recursion.
    maybe your teacher is smarter than you think; it is horribly inefficient to calculate fibonacci numbers with a recursive loop like you just posted.
    hello, internet!

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Try searching this and the C boards, I've posted the solution to the recursive fibonacci problem many times along with an analysis of how it works, why it works, why it's insane, how to fix the insanity, and I've traced the recursion. Can you tell that this is a common question?

    But to answer your question directly, each call to the function must take another step toward the end of the recursive solution, in this case where n is 0 or 1. So n is subtracted for each call, the first call by 1 and the second call by 2 because the first call already subtracted by 1.

    -Prelude
    Last edited by Prelude; 10-26-2002 at 04:42 PM.
    My best code is written with the delete key.

  6. #6
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    This site has a good tutorial on recursion.

    http://www11.brinkster.com/erwnerve/recursion.htm

  7. #7
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Code:
    #include <iostream.h>
    #include <cstdlib>
    using namespace std;
    
    void recurse(int behind, int front) {
    cout << behind << " ";
    if (front > 1000)
    	exit(1);
    	
      recurse((front),(front + behind) ); 
    
    }
    
    int main()
    
    {
    
      recurse(0, 1);        //First function call, so it starts at one
    
      return 0;          
    
    }
    This works

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple question regarding variables
    By Flakster in forum C++ Programming
    Replies: 10
    Last Post: 05-18-2005, 08:10 PM
  2. Simple class question
    By 99atlantic in forum C++ Programming
    Replies: 6
    Last Post: 04-20-2005, 11:41 PM
  3. Simple question about pausing program
    By Noid in forum C Programming
    Replies: 14
    Last Post: 04-02-2005, 09:46 AM
  4. simple question.
    By InvariantLoop in forum Windows Programming
    Replies: 4
    Last Post: 01-31-2005, 12:15 PM
  5. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM