关于递归的一个小疑惑

Question

总共有四个方法, 两个递归方法, 两个循环方法.

我分别用递归A和循环A实现斐波那契数列, 递归B和循环B实现阶乘计算.

可是我很好奇, 同样是计算:

前者中,递归的实现明显比循环实现的性能要低很多(或者说慢很多), 但是后者所用的时间几乎相当(甚至循环还要高点) ?

Answer 1

递归实现斐波那契数列的时候，递归式类似下面的式子：
[align=center][/align]f(n) = f(n-1) + f(n-2)
所以对于每一项f(i)，都可视为一棵二叉树的根节点，层层向下扩展。整个递归树有许多重复的节点，也就意味着许多重复的运算。递归运算本来就存在入栈出栈时间空间消耗的问题，所以重复运算多的时候，开销就大了。
而循环实现斐波那契数列的时候，不存在重复运算的问题。

递归实现阶乘的时候，类似下面的式子：
[align=center][/align]f(n) = n * f(n-1)
不存在每次递归多出一项的问题，跟循环其实没啥区别。