Fibonacci树-计算机程序结构和解释中的递归

Question

在Abelson/Sussman的经典文本“计算机程序的结构和解释”中，在关于树递归和Fibonacci序列的第1.2.2节中，它们显示了这样的图像：

第五斐波那契数计算中的树递归过程

​

​

然后他们写道：“请注意，(fib 3)的整个计算--几乎一半的工作量--都是重复的。实际上，不难证明该过程计算(fib 1)或(fib 0)的次数(通常情况下，上面树中的叶数)是Fib(n +1)。”

我了解到他们提出了一个关于树递归的观点，以及Fibonacci树递归的这个经典案例是如何低效的，因为递归函数两次调用自己：

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

​

​

我的问题是，为什么叶子的数量与序列中的下一个斐波纳契数是相等的(即“不难显示”)？我可以直观地看到是这样的，但是我没有看到为什么叶子的数量(减少的fib 1和fib 0计算)应该是下一个Fibonacci数的指示符(在本例中是8，即Fib 6，即第6个Fibonacci数，即Fib n+1，其中n是5)。

显然，Fibonacci序列是如何计算的--序列中前两个数的和得到当前数，但是为什么叶子数精确地等于序列中的下一个数？这里的联系是什么(除了显而易见的，即观察它并将1和0的叶子相加，实际上，在这种情况下产生了8的总数，这就是下一个斐波那契数，等等)？

Answer 1

“不难展示”比“显而易见”更难。

在两个基本情况下使用归纳。

让我们调用Fib(x)，Fib01(x)中的计算数。

然后,

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

现在假设kFib01(k) = Fib(k+1)：

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

QED。

Answer 2

n=1子句的数目必须等于fib(n)，因为这是非零数的唯一来源，如果某些1s的和等于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叶。inspection.
• N=1:证明树中有fib(N+1)=fib(2)=1叶。检验证明.

归纳步骤:为了计算任意N的fib(N)，我们计算fib(N1)一次，fib(N2)计算一次，并添加它们的结果。通过归纳，树中有fib(N)叶来自我们对fib(N1)的计算，而fib(N-1)的叶子来自我们对fib(N2)的计算。

因此，在我们的整个树中有fib(N) +fib(N1)叶，等于fib(N+1)。QED。

Answer 3

我们可以通过外推来证明这一点。

Fib(0)的叶数= 1，Fib(1)的叶数= 1。

现在，表达式Fib(2)基本上是Fib(1) + Fib(0)的和，即Fib(2) = Fib(1) + Fib(0)。因此，从树本身可以看到，Fib(2)的叶数等于Fib(1)和Fib(0)情况下的叶数之和。因此，Fib(2)的叶数等于2。

接下来，对于Fib(3)，叶数将为Fib(2)和Fib(1)的叶数之和，即2 + 1 = 3

正如您现在所观察到的，这遵循了类似于Fibonacci系列的模式。事实上，如果我们将Fib(n)的叶数定义为FibLeaves(n)，那么我们可以看到，这个系列的Fib(n)是左移1空格。

Fib(n) = 0, 1, 1, 2, 3, 5, 8, 13, 21, ..

FibLeaves(n) = 1, 1, 2, 3, 5, 8, 13, 21, ..

因此，叶子的数量将等于Fib(n + 1)