为什么说递归效率低？

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

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

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

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

（1）对栈的容量压力：

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

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

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

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

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

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

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

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

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

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

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

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