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??

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

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).

Quote:

---

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.

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

This site has a good tutorial on recursion.

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

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