This solves the problem, but how?

The algorithm is recursive. I suggest you read up on what recursion is then walk through the code a bit with some simple test data, you will see then how neat/powerful recursive algorithms can be...if you really want I can explain it to ya, but you will learn more by figuring it out yourself.

And it''s a kinda longish explaination too...

Alex Broadwin
A-Tronic Software & Design
-----
"if you fail in life, you were destined to fail. If you suceed in life, call me."
"The answer is out there."
"Please help, I''m using Windows!"

yeah, that''s where I got this from. The recursion sub-chapter of the book. But your saying recursion is what solves the problem? I''ll look over it again. I thought recursion was just a nested function

Well recursion is a very important and powerful topic, I do suggest ya spend some time with it until you understand it.

Recursion is a problem solving technique. Basic principle is to break down a problem into smaller problems BUT these problems are of exactly the same type as the original problem. Recursion solves a problem by solving a smaller instance of the same problem....Eventually breaking the problem down until an answer can be found.

Example: Simply using recursion to write a string backwards

First thing we have to figure out is what our base case will be. This is a special case whose solution you know. The base case allows the recursive process to break, thus it is very very important. The base case in our example will be the empty string, string length of zero.



The Recursive Function:

void ReverseString( char *str, int size ) {
if( size > 0 ) {
// Write out the last character
cout << str[size-1];

// Write the rest of the string out in reverse by calling this function repeatedly
ReverseString( str, size-1 ); // very important to subtract one from size when making the next recursive call
} // end if string is not the empty string

// size == 0, base case do nothing
} // end ReverseString




Test Data: cat

Initial Call: str = "cat"; size = 3; output = t;

Recursive Call 1: str = "cat"; size = 2; output = a;

Recursive Call 2: str = "cat"; size = 1; output = c;

Recursive Call 3: str = "cat"; size = 0; no output base case reached

Now we "unwind" the recusive calls...

Return to Recursive Call 2: no more code to execute...return

Return to Recursive Call 1: no more code to execute...return

Return to Initial Call: no more code to execute..return

Final Output will be: tac

Hopefully this helps ya out some if not I can try and write up a better explanation, but its alot easier with pen/paper to sketch out the process.

If ya need anything else ya contact me on AIM, Epic70
Good Luck

Do this...

in your head plug in a number and just do a step by step walk through of a number in your head.

All the fibonacci function does is takes the number you pass to it and then adds the two previous numbers. This is done by calling the function again.

This will break down (because your passing n-1 and n-2) to 1 or 0 which then the if statement jumps in and stops calling it self by return 1

Since noone has mentioned it: That algorithm is hopelessly inefficient - try finding the 50th or 100th Fibonacci number with it.

Psalm 137:9: "Happy shall he be, that taketh and dasheth thy little ones against the stones."

quote:

---

Original post by subnet_rx
I can''t figure out where it''s keeping the running total.

---

Effectively, in the call stack.

Superpig
- saving pigs from untimely fates
- sleeps in a ham-mock at www.thebinaryrefinery.cjb.net

ahh, thx for all the explanations. But the last one is what I really needed to know. I knew it was breaking the problem down from the book''s explanation. But it broke it down until thousands of functions were returning 1''s or 0''s. What I couldn''t figure out, was how it was adding the 1''s all together. The call stack can hold a running total of some sort?

You are calling the fibonacci function. The statement

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

is the key. Replace n with the value in the argument and you have two new function calls that has to be handled before returning the value. You will make recursive calls and ends up with something like
n=3
return (fibonacci(2)+fibonacci(1))

fibonacci(1) = n (=1)
fibonacci(2) = fibonacci(1)+fibonacci(0) = n(=1) + n(=0)

thus fibonacci(3)=2

The calls are put on the stack until n=0 or n=1 when they are all pushed off the stack in reverse and the answer will unfold. Neat!

It is not particularily effective but has its moments and is a way to make code less complicated. You have to be careful how many recursive calls you make since you´re filling up the stack. For small problems it is great.

Recursion in itself isnt what makes this algorithm inefficient - its the excessive number of duplicated operations performed. fibonacci( n ) calls fibonacci( n - 1 ), which calls fibonacci( n - 2 ) etc... When fibonacci( n - 1 ) returns from its recursive descent, fibonacci( n - 2 ) is called - again, duplicating the previous call. Now you have two calls to fibonacci( n - 2 ), which in turn each call fibonacci ( n -3 ). In addition fibonacci( n - 1 ) also calls fibonacci( n - 3), meaning we have three calls to fibonacci( n - 3 ) alltogether.
This gets worse and worse the further down we get. Computing fibonacci( 40 ) requires over 300 million recursive calls, which is way excessive considering the basic calculation shouldnt require more than 39 additions.


Psalm 137:9: "Happy shall he be, that taketh and dasheth thy little ones against the stones."

Every time u call a function a block of memory is allocated to that function on the ''call stack'' Each block of memory contains local variables and the function name (its more complex than this also pointers to static parent environment depending on what language u r using an other things).

This means that the last function called along with all of the variables local 2 it will be on the top of the stack. If u call the same function 100 times then there will be 100 blocks dedicated to that function each with (perhaps) different local data. When the function returns or exits the block of data related to that call is destroyed and any results are returned to the callign function ie the next block on the stack.

Hope this helps - if u want 2 know more read about programming language design.