快速递归函数以返回第 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;
}

我是初学者，所以请尽可能详细。

- Amelie Malyan

---

你为什么认为这段代码不应该工作？ - Captain Obvlious

你具体不理解什么？请在问题中详细阐述。 - πάντα ῥεῖ

此函数之所以快速是因为它只在一条路径上进行递归。 - The Paramagnetic Croissant

代码应该是可用的（不是我写的），只是我无法理解其背后的算法。不过，我确实明白它的一般思路，即尝试保存一些斐波那契数，以便进一步使用而不是像简单递归实现一样再次计算。@CaptainObvious - Amelie Malyan

很遗憾，@Bathsheba。它不会立即返回调用的返回值，而是执行后续的加法操作。 - The Paramagnetic Croissant

Answer 1

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

简单递归定义fib的严重低效性在于，在每个递归级别上，您必须进行两个不同的调用以降低级别，即使其中一个包括另一个的所有工作。

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

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

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

编辑（针对您的编辑）：

主要问题是，当我们在prev0中存储垃圾时，fib（n-1，prev0）返回什么？

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

函数签名中的int＆amp;参数声明允许函数根据需要将该参数用作输入或输出或两者兼而有之。这个特定的函数将其用作输出。

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

该级别的n是“按值”传递的，这意味着它是传递的表达式（更高级别的n-1）的值的副本。但是，该级别的prev1通过引用传递，因此它不是更高级别的prev0的值的副本，而是更高级别的prev0的别名。

- JSF

---

加一，但我认为你应该提到尾递归才算是一个完整的答案。 - Bathsheba

非常感谢您的回答，这在某种程度上为我澄清了一些问题（我不知道该函数还返回prev1）。您能否更具体地解释它从哪里获取值并返回。我无法完全理解那部分。 - Amelie Malyan

我们有一个函数声明 int fib(int n, int &prev1)，其中的 & 导致函数内对 prev1 的任何更改都会发生在传递为 prev1 的任何变量上。然后我们在函数内看到了第一次使用 prev1 的语句 prev1 = fib(n – 1, prev0);，它将其设置为递归调用的主要结果。在同一行中，我们看到 prev0 被“传递”到 prev1（但信息流是相反的），因此被调用函数中存储在 prev1 中的值进入了该函数的 prev0。 - JSF

Answer 2

请注意，prev1 从未被读取，只被写入。让我们这样考虑这个函数：

std::pair<int,int> fib_pair(int n) {
    if (n < 2) {
        return std::make_pair(n, 0);
    }

    std::pair<int, int> prev = fib_pair(n-1);
    return std::make_pair(prev.first + prev.second, prev.first);
}

现在更清晰了 - 只有一个递归调用，而 fib(n) 返回前两个数字，而不仅仅是一个数字。因此，我们有一个线性函数，而不是指数函数。然后，我们可以根据这个函数重写原始版本，以帮助我们理解两者：

int fib(int n, int &prev1) {
    std::pair<int, int> pair = fib_pair(n);
    prev1 = pair.second;
    return pair.first;
}

- Barry

---

我认为你在写 return prev.first + prev.second; 的时候，应该是想要写成 return std::make_pair( prev.first + prev.second, prev.first); 这样就可以同时返回 fib(n) 和 fib(n-1) 了。这是因为递归调用已经返回了 fib(n-1) 和 fib(n-2)。 - JSF

@JSF 是的，你说得对。我只是复制了整个函数，并没有改变那一行。 - Barry

Answer 3

让我们来看一下四个不同的函数，使用伪代码计算第n个斐波那契数，而不是限制在单一语言中。第一个遵循标准的递归定义：

function fib(n) # exponential
    if n <= 2 return 1
    return fib(n-1) + fib(n-2)

这个函数需要指数时间，O(2ⁿ)，因为它在每一步重新计算之前计算过的斐波那契数。第二个函数需要线性时间，O(n)，通过从1到n工作而不是从n到1，并跟踪两个先前的斐波那契数。

function fib(n) # linear
    if n <= 2 return 1
    prev2 = prev1 = 1
    k := 3
    while k <= n
        fib := prev2 + prev1
        prev2 := prev1
        prev1 := fib
    return fib

这是您程序使用的相同算法，尽管您的方法通过递归操作并通过指向外部变量的指针传递其中一个参数来掩盖正在进行的操作。

Dijkstra 提出了一种计算第n个斐波那契数列数值的算法，使用矩阵和平方取幂算法，时间复杂度为O(log n)。我在这里不会给出完整的解释；Dijkstra做得比我好（尽管您应该注意他的约定，F₀=1而不是我们一直在做的F₀=0）。下面是算法：

function fib(n) # logarithmic
    if n <= 2 return 1
    n2 := n // 2 # integer division
    if n % 2 == 1 return square(fib(n2+1)) + square(fib(n2))
    return fib(n2) * (2*fib(n2-1) + fib(n2))

第四个算法在常数时间内运行，即O(1)，前提是您拥有具有足够精度的浮点数，使用斐波那契数的数学定义：

function fib(n) # constant
    sqrt5 := sqrt(5)
    p := (1 + sqrt5) / 2
    q := 1 / p
    return floor((p**n + q**n) / sqrt5 + 0.5)

对于大多数语言而言，最后一个算法并不是非常有用，因为要处理任意大小的斐波那契数列，你需要某种无限精度的十进制算术库，虽然它是常数时间，但实际上它可能比简单的对无限精度整数进行对数时间算法操作要慢，至少在n很大时是这样。

- user448810

Answer 4

找到斐波那契数列的显然（非高效）实现方式是：

int fib(int n) {
    if (n<2) return n;
    return fib(n-2) + fib(n-1);
}

这个实现不够高效，你会做两次相同的计算。

例如，如果n是6，该算法会要求你添加fib(4)和fib(5)。 要找到fib(5)，您需要添加fib(4)和fib(3)。 这样，您就第二次计算了fib(4)。 随着n变得更大，这种做法将变得更加低效。

您提供的示例通过记忆先前的斐波那契数列避免了这种低效。

- Olivier De Meulder