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

Question

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

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

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

我知道他们正在就树递归以及斐波那契树递归的这种经典案例是如何效率低下的，因为递归函数调用了自己两次：

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

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

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

标签： recursionschemefibonaccisicp

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

QED。