递归与迭代

Question

如果说在任何地方都使用递归，那么可以使用for循环，对吗？如果递归通常比较慢，那么将其用于循环迭代的技术原因是什么？

如果总是可以将递归转换为for循环，那么有经验法则吗？

Answer 1

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

因为在某些算法中很难迭代求解。尝试以递归和迭代的方式解决深度优先搜索问题。您将得到这样一个想法，即使用迭代来解决DFS是非常困难的。

另一件值得尝试的事情是：尝试以迭代方式编写合并排序。这将花费您相当长的时间。

在任何地方使用递归都可以使用for循环，这样说对吗？

对这条线索对此有很好的答案。

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

相信我。尝试编写自己的版本以迭代方式解决深度优先搜索问题。您会注意到一些问题更容易递归解决。

提示：当你在解决一个可以通过分治技术解决的问题时，递归是很好的。

Answer 2

在任何地方使用递归都可以使用for循环，这样说对吗？

是的，因为大多数CPU中的递归都是用循环和堆栈数据结构建模的。

如果递归通常较慢，那么使用它的技术原因是什么？

它不是“通常较慢”：较慢的是错误应用的递归。最重要的是，现代编译器擅长将一些递归转换为循环，甚至无需询问。

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

为迭代解释时最容易理解的算法编写迭代程序；为递归解释最好的算法编写递归程序。

例如，在许多编程语言中搜索二叉树、运行快速排序和解析表达式通常是递归解释的。这些最好也是递归编码。另一方面，计算阶乘和计算斐波那契数在迭代方面更容易解释。对它们使用递归就像用大锤拍苍蝇：这不是一个好主意，即使大锤做得非常好。

Answer 3

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

一些优化，如尾调用优化，可以使递归更快，但并不总是可能的，并且并非在所有语言中实现。

使用递归的主要原因是

• 在许多情况下，当它模仿我们解决问题的方法时，它会更直观
• 一些数据结构，如树，使用递归更容易探索（或者在任何情况下都需要堆栈）

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