c++ - 返回第 n 个斐波那契数的快速递归函数

Question

谁能解释一下下面的代码是如何工作的。该代码作为返回第 n 个斐波那契数的函数的快速递归实现给出。我对递归函数的工作原理有一个大概的了解。我可以完全理解这种函数的直接递归实现，使用斐波那契数的定义，但是效率不高。我无法理解的主要问题是当我们在 prev0 中存储垃圾时 fib(n – 1, prev0) 返回什么。

int fib(int n, int &prev1) {
    if (n < 2) {
        prev1 = 0;
        return n;
    }
    int prev0;
    prev1 = fib(n – 1, prev0);
    return prev0 + prev1;
}

我是初学者，所以请尽可能具体。

Answer 1

您可能错过了这个函数返回两个结果的事实:一个作为其返回值，一个在通过引用传递的“输入”参数中。

fib 的简单递归定义的严重低效之处在于，在每个递归级别，您必须对较低级别进行两次不同的调用，即使其中一个包含另一个的所有工作。

通过允许包含“其他”所有工作的那个也返回“其他”的结果，您可以避免在每个级别加倍工作。

在数学意义上它不再是一个“函数”(因为有副作用)。但作为编程意义上的函数，它通过一次调用返回两个值来回避 fib 的效率问题。

我认为值得一提的是，在 C++ 中，有更优雅的方法可以将一对值作为函数的结果返回。 (即使在 C 中，您也可以按值返回结构)。

编辑(响应您的编辑):

The main thing I cannot grasp is what does fib(n – 1, prev0) return when we have garbage stored in prev0.

诀窍在于 prev0 是函数的输出，而不是输入。

I am a beginner, so, please, be as specific as you can.

函数签名中int & 的参数声明允许函数将该参数用作它选择的输入或输出或两者。此特定函数将其用作输出。

如果您了解递归函数的基础知识，您就会了解递归的每一层如何拥有自己的参数 n 和局部变量 prev0 的拷贝。但是 prev1 不是一个单独的变量。它实际上是更高级别的 prev0 的别名。因此，当前级别的 prev1 的任何读取或写入实际上都发生在更高级别的 prev0 上。

此级别的 n 是“按值”传递的，这意味着它是所传递表达式值(更高级别的 n-1 )的拷贝。但是本层的prev1是通过引用传递的，所以它不是上层prev0值的拷贝，而是上层prev0的别名。