小编sic*_*fan的帖子

在 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 个）斐波那契数，等等在）？