递归与迭代

Question

说到处都recursion可以使用for循环是否正确？如果递归通常较慢，那么将其用于循环迭代的技术原因是什么？并且如果总是有可能将递归转换为for循环，是否有经验法则？

Answer 1

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

某些优化（例如尾部调用优化）可使递归更快，但并非总是可能的，并且并非所有语言都实现。

使用递归的主要原因是

当它模仿我们对问题的处理方法时，它在许多情况下更加直观

某些数据结构（例如树）更易于使用递归进行探索（或者在任何情况下都需要堆栈）

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

Answer 2

说在各处使用递归都可以使用for循环是否正确？

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

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

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

并且如果总是有可能将递归转换为for循环，是否有经验法则？

编写迭代程序，以便在迭代解释时能最好地理解算法；为算法编写递归程序，最好以递归方式进行解释。

例如，经常以递归方式解释搜索二叉树，运行快速排序以及解析许多编程语言中的表达式。这些也是最好的递归编码。另一方面，就阶乘而言，计算阶乘和计算斐波纳契数更容易解释。使用递归对他们来说就像是用大锤乱打苍蝇：这不是一个好主意，即使在大锤它做了很好的工作+。

+我借用了迪克斯特拉（Dijkstra）的“编程学科”中的大锤类比。

Answer 3

题 ：

如果递归通常较慢，那么将其用于循环迭代的技术原因是什么？

答：

因为在某些算法中很难迭代求解。尝试以递归和迭代的方式解决深度优先搜索。您会发现很难用迭代来解决DFS。

可以尝试的另一件好事：尝试写Merge进行迭代排序。这将花费您很多时间。

题 ：

说在各处使用递归都可以使用for循环是否正确？

答：

是。这个线程对此有很好的答案。

题 ：

并且如果总是有可能将递归转换为for循环，是否有经验法则？

答：

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

提示：当您解决可以通过分治法解决的问题时，递归非常有用。