说在任何地方都使用递归是否for可以使用循环？如果递归通常较慢，那么在for循环迭代中使用它的技术原因是什么？
如果总是可以将递归转换为for循环，是否有经验法则来做到这一点？
问问题
114645 次
10 回答
161
递归通常要慢得多，因为所有函数调用都必须存储在堆栈中以允许返回给调用者函数。在许多情况下，必须分配和复制内存以实现范围隔离。
一些优化，如尾调用优化，使递归更快，但并非总是可行，并且并非在所有语言中都实现。
使用递归的主要原因是
- 当它模仿我们解决问题的方法时，它在许多情况下更直观
- 使用递归更容易探索一些数据结构，如树（或者在任何情况下都需要堆栈）
当然，每个递归都可以建模为一种循环：这就是 CPU 最终要做的事情。而递归本身，更直接地，意味着将函数调用和作用域放在堆栈中。但是将递归算法更改为循环算法可能需要大量工作并使代码的可维护性降低：对于每次优化，只有在某些分析或证据表明有必要时才应尝试。
于 2013-03-28T17:15:59.363 回答
60
说到处都使用递归是否可以使用 for 循环？
是的，因为大多数 CPU 中的递归都是用循环和堆栈数据结构建模的。
如果递归通常较慢，那么使用它的技术原因是什么？
它不是“通常较慢”：错误应用的递归更慢。最重要的是，现代编译器擅长将一些递归转换为循环，甚至无需询问。
如果总是可以将递归转换为 for 循环，是否有经验法则来做到这一点？
为迭代解释时最容易理解的算法编写迭代程序；为最好用递归方式解释的算法编写递归程序。
例如，搜索二叉树、运行快速排序和解析许多编程语言中的表达式通常是递归解释的。这些最好也是递归编码的。另一方面，计算阶乘和计算斐波那契数在迭代方面更容易解释。对它们使用递归就像用大锤拍苍蝇：这不是一个好主意，即使大锤做得非常好+。
+我从 Dijkstra 的“编程学科”中借用了大锤类比。
于 2013-03-28T17:15:03.023 回答
30
问题 ：
如果递归通常较慢，那么在循环迭代中使用它的技术原因是什么？
回答 ：
因为在某些算法中很难迭代地解决它。尝试以递归和迭代的方式解决深度优先搜索。你会明白用迭代来解决 DFS 是很困难的。
另一个值得尝试的好东西：尝试迭代地编写合并排序。这将花费你相当长的时间。
问题 ：
说到处都使用递归是否可以使用 for 循环？
回答 ：
是的。这个线程对此有一个很好的答案。
问题 ：
如果总是可以将递归转换为 for 循环，是否有经验法则来做到这一点？
回答 ：
相信我。尝试编写自己的版本来迭代地解决深度优先搜索。你会注意到一些问题更容易递归解决。
提示：当您解决可以通过分而治之技术解决的问题时，递归是很好的。
于 2013-03-28T17:15:38.033 回答
4
除了较慢之外，递归还可能导致堆栈溢出错误，具体取决于它的深度。
于 2014-02-06T18:15:15.393 回答
3
要使用迭代编写等效方法，我们必须显式使用堆栈。迭代版本的解决方案需要一个堆栈这一事实表明该问题足够困难，可以从递归中受益。作为一般规则，递归最适用于无法用固定内存量解决的问题，因此在迭代解决时需要堆栈。话虽如此，递归和迭代可以显示相同的结果，但它们遵循不同的模式。要根据具体情况决定哪种方法效果更好，最佳实践是根据问题遵循的模式进行选择。
例如，要找到三角形序列的第 n 个三角形数： 1 3 6 10 15 ... 使用迭代算法找到第 n 个三角形数的程序：
使用迭代算法：
//Triangular.java
import java.util.*;
class Triangular {
public static int iterativeTriangular(int n) {
int sum = 0;
for (int i = 1; i <= n; i ++)
sum += i;
return sum;
}
public static void main(String args[]) {
Scanner stdin = new Scanner(System.in);
System.out.print("Please enter a number: ");
int n = stdin.nextInt();
System.out.println("The " + n + "-th triangular number is: " +
iterativeTriangular(n));
}
}//enter code here
使用递归算法：
//Triangular.java
import java.util.*;
class Triangular {
public static int recursiveTriangular(int n) {
if (n == 1)
return 1;
return recursiveTriangular(n-1) + n;
}
public static void main(String args[]) {
Scanner stdin = new Scanner(System.in);
System.out.print("Please enter a number: ");
int n = stdin.nextInt();
System.out.println("The " + n + "-th triangular number is: " +
recursiveTriangular(n));
}
}
于 2017-02-18T02:54:39.107 回答
1
大多数答案似乎都假设iterative= for loop。如果您的 for 循环不受限制（如C，您可以使用循环计数器做任何您想做的事情），那么这是正确的。如果它是一个真正的 for循环（比如在 Python 或大多数无法手动修改循环计数器的函数式语言中），那么它是不正确的。
所有（可计算的）函数都可以递归和使用while循环（或条件跳转，它们基本上是相同的）来实现。如果你真的把自己限制在for loops，你只会得到这些函数的一个子集（原始递归函数，如果你的基本操作是合理的）。诚然，它是一个相当大的子集，恰好包含您在实践中可能遇到的每一个功能。
更重要的是，很多函数很容易递归实现，而迭代实现非常困难（手动管理调用堆栈不算在内）。
于 2014-02-06T23:55:57.673 回答
0
我似乎记得我的计算机科学教授曾经说过，所有具有递归解决方案的问题也都有迭代解决方案。他说递归解决方案通常速度较慢，但是当它们比迭代解决方案更容易推理和编码时，它们经常被使用。
但是，对于更高级的递归解决方案，我不相信它总是能够使用简单的for循环来实现它们。
于 2013-03-28T17:15:47.113 回答
-4
与纯迭代方法相比，递归+记忆可能导致更有效的解决方案，例如检查：http: //jsperf.com/fibonacci-memoized-vs-iterative-for-large-n
于 2015-11-13T14:05:04.557 回答
-6
简短的回答：折衷是递归更快，并且在几乎所有情况下 for 循环占用的内存更少。但是，通常有一些方法可以更改 for 循环或递归以使其运行得更快
于 2013-03-29T04:36:03.357 回答