My mind is not able to understand how the value is returned from this simple recursive algorithm. The algorithm is as follows:
int fib(int n)
{
if (n <= 1)
return n;
return fib(n-1) + fib(n-2);
}
I am wondering how inputting 5 to this function returns 5? I know that the fifth Fibonacci number is 5 so this is the correct answer but I am unsure how this answer is derived from the code above. First five fibonacci numbers: 1 1 2 3 5.
From my limited understanding I think passing 5 to this function would return 7. This is because 5-1 = 4 and 5 - 2 = 3. Then adding these two numbers together I obtain the simple integer 7. Did this make sense? I am sure I already lost someone reading this though this is very simple. If I was reading this I would be lost.
Also, if I make a recursion tree and show the recursive calls to fib starting from 5 I do not see how this eventually returns 5, but I do see all the calls to the function fib() until eventually 1 is returned because the argument to fib() is 0 or 1. The recursion tree I drew is just a copy of the one shown at this page.
Can one help me understand this recursive algorithm?