Fibonacci调用堆栈中叶子与总节点的比率

Question

如果你要看一个计算第n个Fibonacci数的递归实现(根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.

Answer 2

fib(x)由叶纤维(x-1)和纤维叶(x-2)组成.因此,您获得与斐波那契数相同的递归方程.

如果终止点(叶子)是Fib1和Fib0,那么

tree   numofleaves
fib2   2
fib3   3
fib4   5
fib5   8
fib6   13
...

和numofleaves(x)= fib(x + 1).

对于节点数,您可以得到方程numnodes(x)= 1 + numnodes(x-1)+ numnodes(x-2).