c++ - 值是如何返回的？ - 递归算法

Question

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

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

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

}

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

根据我有限的理解，我认为将 5 传递给此函数将返回 7。这是因为 5-1 = 4 和 5 - 2 = 3。然后将这两个数字相加，我得到简单的整数 7。这是否有意义？我敢肯定我已经失去了阅读这篇文章的人，尽管这很简单。如果我正在读这篇文章，我会迷路的。

此外，如果我制作一个递归树并显示从 5 开始对 fib 的递归调用，我看不到这最终如何返回 5，但我确实看到了对函数 fib() 的所有调用> 直到最终返回 1，因为 fib() 的参数是 0 或 1。我画的递归树只是这个 page 中所示树的拷贝。 .

谁能帮我理解这个递归算法？

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