algorithm - 斐波那契调用堆栈中叶子与总节点的比率

Question

如果您要查看计算第 n 个斐波那契数(根 100，子代 99 和 98，孙代 98、97、97 和 96 等)的递归实现，大致比率是多少递归树中的叶子数占总节点数？

    100
   /   \
  98   97
 /  \   .
96  97  .
.    .  .
.    .  

不是家庭作业，只是学术上的好奇。 (是的，我意识到递归实现是一种非常糟糕的计算斐波那契数的方法)

Answer 1

叶子的数量就是 F(n)，因为 F(i) 就是该节点下的叶子数量。你知道为什么吗？ (提示:使用归纳法)

非叶​​子节点数为叶子节点数-1。这是二叉树的一个特性。所以节点总数是F(n) + F(n)-1 = 2F(n)-1。

随着 n 变大，该比率因此接近 1/2。