斐波那契树-计算机程序结构和解释中的递归

Question

在 Abelson/Sussman 的经典著作《计算机程序的结构和解释》中，在有关树递归和斐波那契数列的第 1.2.2 节中，他们展示了这个图像：

计算第五个斐波那契数时生成的树递归过程

然后他们写道：“请注意，整个计算(fib 3)（几乎一半的工作）是重复的。事实上，不难证明该过程将计算的次数(fib 1)或(fib 0)（上述树中的叶子数，在一般）正是Fib(n + 1)。”

我知道他们正在阐述树递归的观点，以及斐波那契树递归的经典案例如何效率低下，因为递归函数调用自身两次：

用于计算斐波那契数的树递归函数

我的问题是，为什么叶子的数量等于序列中的下一个斐波那契数是显而易见的（即“不难证明”） ？我可以直观地看到情况确实如此，但我没有看到为什么叶数（减少的向下fib 1和fib 0计算）应该是下一个斐波那契数的指标（在本例中为 8，即斐波那契数）之间的联系6，即第6个斐波那契数，即Fib n+1，其中n为5）。

很明显斐波那契数列是如何计算的 - 序列中前两个数字的总和产生当前数字，但为什么叶子的数量恰好等于序列中的下一个数字？那里有什么联系（除了明显的联系之外，事实上，在这种情况下，查看它并将 1 和 0 叶相加确实会产生总计数 8，这是下一个（第 6 个）斐波那契数，等等在）？

Answer 1

“不难表现”比“显而易见”更难。

对两个基本案例使用归纳法。我们将,
中的计算次数称为。 然后，Fib(x)Fib01(x)

Fib01(0) = 1 by definition, which is Fib(1) 
Fib01(1) = 1 by definition, which is Fib(2)

现在假设Fib01(k) = Fib(k+1)k < n：

Fib01(n) = Fib01(n-1) + Fib01(n-2) 
         = Fib(n) + Fib(n-1) 
         = Fib(n+1) by definition

量子ED。

Answer 2

n=1 子句的数量必须等于 fib(n)，因为这是非零数字的唯一来源，并且如果某些数量的 1 的总和等于 fib(n)，则必须有其中 fib(n) 个。

由于 fib(n+1) = fib(n) + fib(n-1)，我们只需要证明有 fib(n-1) 个叶子计算 fib(0) 即可。对我来说，如何展示这一点不太明显，但也许它归纳出前一个案例？

也许更简单的方法是归纳地完成整个事情。

对于我们的基本情况：

• N=0：树中有 fib(N+1)=fib(1)=1 个叶子。通过检查证明。
• N=1：树中有 fib(N+1)=fib(2)=1 个叶子。通过检查证明。

归纳步骤：为了计算任意 N 的 fib(N)，我们计算一次 fib(N-1)，一次计算 fib(N-2)，并将它们的结果相加。通过归纳，树中有 fib(N) 个叶子来自我们对 fib(N-1) 的计算，树中有 fib(N-1) 个叶子来自我们对 fib(N-2) 的计算。

因此，我们的整个树中有 fib(N) + fib(N-1) 个叶子，等于 fib(N+1)。量子ED。