How is the value returned? - recursive algorithm

Question

My mind cannot 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 to enter 5 for this function 5? I know that the fifth Fibonacci number is 5, so this is the correct answer, but I'm not sure how this answer is obtained from the code above, The first five Fibonacci numbers: 1 1 2 3 5.

From my limited understanding, I think going over 5 to this function will return 7. This is because 5-1 = 4 and 5 - 2 = 3. Then, adding these two numbers together, I get a simple integer 7. Did that make sense? I am sure that I have already lost someone reading this, although it is very simple. If I read this, I would be lost.

Also, if I create a recursion tree and show recursive calls to fib starting from 5, I don’t see how it ultimately returns 5, but I see all calls to the fib() function until 1 is returned, therefore that the fib() argument is 0 or 1. The recursion tree I painted is just a copy of the one shown on this page .

Can I understand this recursive algorithm?

Answer 1

So open 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 correct that 5-1 = 4 and 5-2 = 3, but that means that you call fib(4) + fib(3) = 5 , which is very different from 4 + 3 = 7

Answer 2

Here is 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 

Answer 3

Think about returning by returning a number, and to get that number, it must call a function and run that function. And he does this until he reaches the base case, n = 0 or 1, then he does not call another function to return the number.

Answer 4

When using a recursive function, an implicit stack is supported that keeps track of the values ​​returned from each recursive call.

Now consider your example for a given value 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 requests a search number on line 15 and assigns a target number to this number. Then it calls fib () with the target. Running branches to the fib () function, where on line 28 it prints its argument.

The argument n is checked to ensure that it is 1 or 2 on line 30; if so, returns fib (). Otherwise, it returns the sum 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 proceeds to the function fib (), and n is checked 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.

Since fib (4) passes into an argument that is at least 3, fib () will be called again, this time from 3 and 2. fib (3) will in turn call fib (2) and fib (1). Finally, calls to fib (2) and fib (1) will return 1 because these are stopping conditions.