Explanation on Fibonacci Recursion

Question

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

Answer 1

It doesn't return a value each time, at least not immediately.

Every time the method calls itself, it places the new call on a stack. There's limited space on this stack, so a big number with enough recursive calls will throw a stackoverflow exception. That's also why you have this terminating condition, that tells it when to stop calling itself.

if (n <= 2)  
{   
    return 1;  
}

After your method calls itself for the very last time on each branch of the tree (when n <= 2 and the method returns 1 instead of calling itself), it will unwind the stack, finally evaluating all of those calls and summing up the return values, returning 13 in the case of Fib(7).