How is the value returned? - recursive algorithm

Question

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?

Answer 1

Ok, let's open up the recursion for fib(5)

fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0

fib(1) + fib(0) = 1 + 0 = 1 so fib(2) = 1
fib(2) + fib(1) = 1 + 1 = 2 so fib(3) = 2
fib(3) + fib(2) = 2 + 1 = 3 so fib(4) = 3
fib(4) + fib(3) = 3 + 2 = 5 so fib(5) = 5

You are right that 5-1 = 4 and 5-2 = 3, but that only means you are calling fib(4) + fib(3) = 5 which is very different from 4 + 3 = 7