如何返回值？-递归算法

Question

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

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

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

}

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

据我有限的理解，我认为把5传递给这个函数会返回7。这是因为5-1 =4和5-2= 3。然后把这两个数字相加，我得到了简单的整数7。这有意义吗？我相信我已经失去了一个人读这个，虽然这是非常简单的。如果我读了这篇文章，我会迷路的。

另外，如果我创建一个递归树，并从5开始显示对fib的递归调用，我不知道它最终是如何返回5的，但我确实看到了对函数fib()的所有调用，直到最终返回1为止，因为对fib()的参数是0或1。我绘制的递归树只是这个页面中显示的一个副本。

一个人能帮助我理解这个递归算法吗？

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

Answer 3

将返回看作返回一个数字，为了得到这个数字，它必须调用一个函数并运行该函数。它这样做，直到达到一个基本情况，n=0或1，然后它不会调用另一个函数来返回一个数字。