recursion - Fibonacci Tree-Recursion in Structure and Interpretation of Computer Programs

Question

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

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



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

我知道他们在说明树递归以及斐波那契树递归的这个经典案例是如何效率低下的，因为递归函数会调用自己两次:

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



我的问题是，为什么很明显(即“不难证明”)叶子的数量等于序列中的下一个斐波那契数？我可以直观地看到情况确实如此，但我没有看到为什么叶子的数量(减少的 fib 1 和 fib 0 计算)应该是下一个斐波那契数的指标(在这个case 8，即 Fib 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

QED。