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

Question

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

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

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

我了解斐波那契数列是什么，我了解递归函数的作用以及该函数的工作原理。我只是无法理解 为什么 它有效。我知道当你分解它时，你实际上是在添加一堆 0 和 1，如图所示。

fibonacci recursive

但为什么当我将一个 5 传递给函数并添加所有 0 和 1 时，它会等于 Fibonacci 数列中的第 5 个序号？我以前见过这个问题，但从未真正解释过。回复都是"because recursion"。是的，我知道递归函数是什么以及它是如何工作的。但是为什么这个递归函数会给出正确的斐波那契数列？

Answer 1

请记住，递归的工作原理是分解问题直到我们知道答案是什么，然后从那里构建它。

我们对斐波那契数列了解多少？

我们知道当：

x = 1 和 x = 0

这是最低的。那是一把重要的钥匙。因为当 x = 0 时，我们实际上是在做 0 + 0，而当 x = 1 时，我们实际上是在做 0 + 1。现在从顶部开始。

0,1,1,2,3,5,8,13...

如果我们在 13 点，13 点是多少？为什么只是 5 + 8 对呢？所以这就是

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

来自。因为这些将越来越低地分支，直到我们处于每个的基本情况下。

这是递归调用。因为现在该方法要回到堆栈并再次调用 fibRec。您会注意到 (n-1) 和 (n-2) 都加在一起并设置为 i。这样我们就不会失去价值。由于 + 符号，堆栈最终会返回越来越多的 (n-1) 和 (n-2)，直到我们处于基本情况。我希望所有这些都有意义。递归思考可能非常困难。这是从上到下的视觉表示。

简而言之。这只是不断地将前面的斐波那契序列添加到当前序列，直到它到达当前循环。

Answer 2

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

F(0) ≡ 0
F(1) ≡ 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
...
F(n) = F(n - 1) + F(n - 2) ∀ n > 1

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

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

我相信你知道所有这些，但我认为将这部分作为参考将有助于我的解释。

1 和 0 的来源

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

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

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

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

我们现在已经根据 F(1) ≡ 1 和 F(0) ≡ 0（两者都是已知的）得到了 F(2)，因此我们能够计算出一个实际值而不是执行更多递归。

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

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

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

现在，如果将所有的 1 相加，则总和为 8，因此 F(6) = 8，这是正确的！

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

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

Why does the fibonacci recursive sequence work?

recursion

function

fibonacci

1 和 0 的来源