I must understand something about this. It seems like there is no good guide to explain explicitly. What does the function tree look like?
static long Fib(int n)
{
if (n <= 2)
{
return 1;
}
return Fib(n - 1) + Fib(n - 2);
}
Assuming I do Fib(7)
, I actually understand that it should look like this:
The thing is that it seems like the tree is presented as if fib(7)
actually means fib(6)
+ fib(5)
which should be true.... However, if I understand recursion than fib(7)
is actually fib(6)
+ fib(5)
but fib(5)
isn't operated yet since fib(6)
will now call itself to fib(4)
+ fib(3)
and once again fib(3)
won't be executed since fib(4)
will call itself until it stops at the "stop" condition... and than what?
If fib(7)
calls fib(6)
and so on..... until fib(1)
, what about all of the other fib(n-2)
functions?
How does it actually returns each time the result and tell me what is the value of fib(7)
?
f(6)
it will be added at top of the stack whilef(7)
is underf(6)
. after finishingf(6)
it will removef(6)
from stack and now you can continue inf(7)
because you had all the needed information stored in stack to continue...