总共有四个方法, 两个递归方法, 两个循环方法.
我分别用递归A和循环A实现斐波那契数列, 递归B和循环B实现阶乘计算.
可是我很好奇, 同样是计算:
前者中,递归的实现明显比循环实现的性能要低很多(或者说慢很多), 但是后者所用的时间几乎相当(甚至循环还要高点) ?
递归实现斐波那契数列的时候，递归式类似下面的式子：
[align=center][/align]f(n) = f(n-1) + f(n-2)
所以对于每一项f(i)，都可视为一棵二叉树的根节点，层层向下扩展。整个递归树有许多重复的节点，也就意味着许多重复的运算。递归运算本来就存在入栈出栈时间空间消耗的问题，所以重复运算多的时候，开销就大了。
而循环实现斐波那契数列的时候，不存在重复运算的问题。
递归实现阶乘的时候，类似下面的式子：
[align=center][/align]f(n) = n * f(n-1)
不存在每次递归多出一项的问题，跟循环其实没啥区别。
[quote="Ithaca"]但是后者所用的时间几乎相当(甚至循环还要高点) ?
[/quote]
是不是描述有问题，你是不是想说“甚至比循环还要高点？”
递归慢是正常的，因为递归比循环多了很多栈操作（因为要不断地调用函数）。
但你说后者循环性能差就奇怪了，不帖代码大家也没法回答你吧。
我看了半天也没看懂最后一句话是什么意思。
想起一个同事说的一句话，“你做的饭不仅好看，而且难吃”。
递归与循环比较快慢，主要是递归中是否涉及到重复计算，斐波那契递归涉及到重复计算，因此比循环慢。计算阶层不涉及重复计算，所以速度和循环差不多。to liyiwen007 ：因此并不是所有的递归都慢。快慢得从复杂度分析开始
递推在虚拟机层面就是要将递归方法和参数不停地压湛（java每个线程有一个自己的java栈，对方法的调用实际上就是将方法的栈帧入栈），这样的代价是很客观的。而循环是在同一个栈帧中通过反复执行一个代码段并加上一些跳转（类似于goto）逻辑实现的。