价值是如何回报的？ - 递归算法

Question

我的想法无法理解这个简单的递归算法如何返回值.算法如下:

int fib(int n)
{
     if (n <= 1)
         return n;

     return fib(n-1) + fib(n-2);

}

我想知道如何输入5到这个函数返回5？我知道第五个Fibonacci数是5,所以这是正确的答案,但我不确定这个答案是如何从上面的代码中得出的.前五个斐波纳契数:1 1 2 3 5.

从我有限的理解,我认为传递5到这个函数将返回7.这是因为5-1 = 4和5 - 2 = 3.然后将这两个数字加在一起我得到简单的整数7.这有意义吗？我确信我已经失去了读这个的人,虽然这很简单.如果我正在读这篇文章,我就会迷失方向.

此外,如果我创建一个递归树并显示从5开始递归调用fib我没看到它最终如何返回5,但我确实看到函数的所有调用,fib()直到最终返回1,因为参数fib()为0或我绘制的递归树只是本页所示的递归树的副本.

可以帮我理解这种递归算法吗？

Answer 1

好吧,让我们打开递归 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

你是正确的5-1 = 4和5-2 = 3,但这只意味着你正在呼唤fib(4) + fib(3) = 5哪个是非常不同的4 + 3 = 7

Answer 2

这是我的递归调用树版本:

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