How is the value returned? - recursive algorithm

5
votes

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?

4
c++algorithmrecursion
If you're trying to understand recursion, I'd start with an easier example. A recursive factorial function would probably be easier to understand. - Carcigenicate
It doesn't say return (n-1) + (n-2);. It says return fib(n-1) + fib(n-2);. In other words, with n == 5 it's doing return fib(4) + fib(3);. - François Andrieux
@FrançoisAndrieux - but what are fib(4) and fib(3), broken down into recursive calls? :-) - Bob Jarvis - Reinstate Monica
Did you check the values of the nodes of your tree? Sum them up: fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1) will turn to be = 5 - Khalil Khalaf
If I add up all the ones from the tree then yes it does actually equal 5! Wow! Thank-you for the comment. Very helpful... - user3870315

4 Answers

7
votes

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

5
votes

Here's my version of the recursive call tree:

fib(5) = fib(4)                                     + fib(3)

         |                                            |
         +--------------------------\                 +-----------------\
         |                          |                 |                 |

       = fib(3)                   + fib(2)          + fib(2)          + fib(1)

         |                          |                 |                 |
         +-----------------\        +--------\        +--------\        |
         |                 |        |        |        |        |        |

       = fib(2)          + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + 1

         |                 |        |        |        |        |        |
         +--------\        |        |        |        |        |        |
         |        |        |        |        |        |        |        |

       = fib(1) + fib(0) + 1      + 1      + 0      + 1      + 0      + 1

         |        |        |        |        |        |        |        |
         |        |        |        |        |        |        |        |
         |        |        |        |        |        |        |        |

       = 1      + 0      + 1      + 1      + 0      + 1      + 0      + 1

       = 5
2
votes

Think of the return as returning a number, and in order to get that number, it has to call a function and run that function. And it does this until it reaches a base case, n = 0 or 1, then it does not call another function to return a number.

0
votes

When a recursive function is used an implicit stack is maintained that keeps track of values returned from each recursive call.

Now let's consider your example for given value of n=5

>Processing fib(5)... Call fib(3) and fib(4).
>Processing fib(3)... Call fib(1) and fib(2).
>Processing fib(1)... Return 1!
>Processing fib(2)... Return 1!
>Processing fib(4)... Call fib(2) and fib(3).
>Processing fib(2)... Return 1!
>Processing fib(3)... Call fib(1) and fib(2).
>Processing fib(1)... Return 1!
>Processing fib(2)... Return 1!
>5 is the 5th Fibonacci number

Analysis: The program asks for a number to find on line 15 and assigns that number to target. It then calls fib() with the target. Execution branches to the fib() function, where, on line 28, it prints its argument.

The argument n is tested to see whether it equals 1 or 2 on line 30; if so, fib() returns. Otherwise, it returns the sums of the values returned by calling fib() on n-2 and n-1.

In the example, n is 5 so fib(5) is called from main(). Execution jumps to the fib() function, and n is tested for a value less than 3 on line 30. The test fails, so fib(5) returns the sum of the values returned by fib(3) and fib(4). That is, fib() is called on n-2 (5 - 2 = 3) and n-1 (5 - 1 = 4). fib(4) will return 3 and fib(3) will return 2, so the final answer will be 5.

Because fib(4) passes in an argument that is not less than 3, fib() will be called again, this time with 3 and 2. fib(3) will in turn call fib(2) and fib(1). Finally, the calls to fib(2) and fib(1) will both return 1, because these are the stop conditions.