为什么斐波那契递归序列有效？

Question

我想知道为什么这个斐波那契递归函数有效：

int fibRec(int n)
{
    if ((n == 1) || (n == 0))
    {
        return n;
    }

    int i = fibRec(n - 1) + fibRec(n - 2);
    return i;
}

我了解斐波那契数列是什么，也了解递归函数的作用以及该函数的工作原理。我只是很难理解它为什么有效。我知道，当你将其分解时，你本质上是添加了一堆 0 和 1，如下图所示。

斐波那契递归

但为什么当我将 5 传递给函数并将所有 0 和 1 添加后，它会等于斐波那契数列中的第 5 个数呢？我以前见过这个问题，但从未真正解释过。答案都只是“因为递归”。是的，我知道什么是递归函数以及它是如何工作的。但是为什么这个递归函数会给出正确的斐波那契数列呢？

Answer 1

在斐波那契数列中，前两个数字是零和一。这些后面的每个数字都是前两个数字的总和。所以前几个数字是

\n

F(0) \xe2\x89\xa1 0\nF(1) \xe2\x89\xa1 1\nF(2) = F(1) + F(0) = 1 + 0 = 1\nF(3) = F(2) + F(1) = 1 + 1 = 2\nF(4) = F(3) + F(2) = 2 + 1 = 3\nF(5) = F(4) + F(3) = 3 + 2 = 5\nF(6) = F(5) + F(4) = 5 + 3 = 8\n...\nF(n) = F(n - 1) + F(n - 2) \xe2\x88\x80 n > 1\n

\n

因此，当我们递归计算斐波那契数时，我们必须练习以下逻辑过程（出于对 StackOverflow 的尊重，采用伪代码）。

\n

Integer NthFibonacci(Integer n) {\n    if (n < 0) {\n        return undefined;\n    } else if (n < 2) {\n        return n;\n    } else {\n        return NthFibonacci(n - 1) + NthFibonacci(n - 2);\n    }\n}\n

\n

我相信您知道这一切，但我认为将此部分作为参考将有助于我的解释。

\n

1 和 0 出现的地方

\n

解释这一点的最好方法可能是举个例子。

\n

想象一下，如上所述，我们正在尝试递归计算F(6)。尝试按照上面给出的步骤进行操作。请记住，只有当 n > 1 时我们才会执行递归。

\n

首先我们从 开始F(6) = F(5) + F(4)。\n
然后我们找到F(5) = F(4) + F(3)。\n
然后我们找到F(4) = F(3) + F(2)。\n
然后我们找到F(3) = F(2) + F(1)。\n
然后我们找到F(2) = F(1) + F(0)。

\n

这就是事情开始解决的地方！

\n

我们现在已经F(2)得到F(1) \xe2\x89\xa1 1了F(0) \xe2\x89\xa1 0两者都是已知的），因此我们能够计算实际值而不是执行更多递归。

\n

我们现在可以找到F(2) = F(1) + F(0) = 1 + 0 = 1.

\n

注意 1 和 0当人们说整个事情归结为 1 和 0 时，他们所谈论的就是这些。每次我们递归寻找基值时，我们最终都会找到F(2) = 1 + 0。当我们向后移动递归树时，这会导致更多的 1 和 0，从而能够计算出越来越高的值，如下所示。

\n

F(3) = F(2) + F(1) = (1 + 0) + 1\nF(4) = F(3) + F(2) = ((1 + 0) + 1) + (1 + 0)\nF(5) = F(4) + F(3) = (((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)\nF(6) = F(5) + F(4) = ((((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)) + (((1 + 0) + 1) + (1 + 0))\n

\n

现在，如果将所有 1 加起来，总和就是 8，所以F(6) = 8，这是正确的！

\n

这就是它的工作原理，这就是它分解为 1 和 0 的方式。

\n