递归与迭代

Question

凡是使用递归的地方都可以使用for循环，这是正确的吗？如果递归通常较慢，那么在for循环迭代中使用递归的技术原因是什么？

如果总是可以将递归转换为for循环，那么是否有经验法则可以做到这一点？

Answer 1

递归通常要慢得多，因为所有函数调用都必须存储在堆栈中，以便返回到调用者函数。在许多情况下，必须分配和复制内存才能实现作用域隔离。

一些优化，如tail call optimization，使递归更快，但并不总是可行的，并且并不是在所有语言中都实现。

使用递归的主要原因是

• 表示，在许多情况下，它更直观，因为它模仿了我们对problem
• 的方法，即使用递归更容易探索像树这样的数据结构(或者在任何情况下都需要堆栈)

当然，每个递归都可以建模为一种循环:这是CPU最终要做的事情。而递归本身，更直接地意味着将函数调用和作用域放入堆栈中。但是，将递归算法更改为循环算法可能需要大量的工作，并且会使代码的可维护性降低:对于每个优化，只有在分析或证据表明有必要时才应尝试。

Answer 2

问题:

和如果递归通常较慢，那么使用它进行循环迭代的技术原因是什么？

答案:

因为在一些算法中很难迭代地解决它。尝试在递归和迭代中解决深度优先搜索。你会得到这样的想法:用迭代来解决DFS是非常困难的。

另一个值得尝试的好方法是:尝试迭代地编写合并排序。这会花你相当长的时间。

问题:

说只要使用递归，就可以使用for循环，这样说对吗？

答案:

是。这个thread对此有一个非常好的答案。

问题:

如果总是可以将递归转换为

循环，是否有经验法则可以做到这一点？

答案:

请相信我。尝试编写自己的版本来迭代地解决深度优先搜索问题。你会注意到，有些问题更容易递归解决。

提示:当你正在解决一个可以用技术解决的问题时，递归是很好的。

Answer 3

除了速度较慢之外，递归还会导致堆栈溢出错误，具体取决于递归的深度。