为什么说递归效率低？

对于递归，有人提到了两点：

（1）对栈的容量的压力。

（2）个别问题的递归解法，其算法的低效性。

这两个因素我简短点评下，

（1）对栈的容量压力：

通常递归的深度很大造成的。对于这一点当然应该有程序员编码时，来衡量和把握。win32 中一个新建的线程，默认的栈通常在 1 MB 大小。那么如果你的递归函数，深度很大，显然程序员应该对这种情况有预估，和对风险的避免。

这就和你选择，把内存分配在栈上还是堆上，会考虑到分配的内存大小的因素一样。

当然，如果在函数内分配很大的栈上空间，在函数体内定义一个很大的数组，这样不需要很深的深度，也会让栈溢出。这当然也是程序员自己应该控制的。

（2）个别问题的递归解法，算法的低效。

这个低效主要在于这个问题的算法本身。而不是在递归这种方法上。比如说求斐波那契的某一项，子问题会大量重复出现，会产生很多重复计算，这个是很多算法书上，是用来引导出动态规划或者查表法的。

这主要是算法本身的效率问题，而不是递归的问题。这一点是必须应该明确的。

（3）我们可以看到，在和树有关的算法中，经常会有递归函数。

例如，遍历文件夹，删除注册表的某一个 key （及其所有子key）。

尤其对一般树的前序，后序遍历，二叉树的中序遍历。

这主要原因是因为树的定义，就是“递归性”的：

树就是，某一个节点有多个子节点，每个子节点是一个树。

我们再此可以看到，递归的显著优点，是对解的描述的直观性，代码的简洁性。

以下是比较全面的解释，可以看看。 递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。 递归算法解决问题的特点： (1) 递归就是在过程或函数里调用自身。 (2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。 (3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。 (4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。

从机器的硬件性能上讲，循环的效率高一些。

递归涉及到的内存 *** 作肯定要比循环复杂，最主要的就是递归调用函数中的变量的压栈、出栈 *** 作，如果递归的层次太多肯定会导致内存溢出、系统崩溃。例如：计算 n !，如果 n 太大了的话，就不能够使用递归的方法来实现了。就必须将递归的方法修改为非递归方式，这个现在在数据结构教材上都会有讲解的。当然了，递归的最大好处就是：编写代码简单，程序可读性好。

---