小开

所有使用递归的地方都可以使用 for 循环，这样说对吗？

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

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

它不是“通常较慢”: 是递归不正确地应用，这是较慢的。最重要的是，现代编译器擅长在不需要询问的情况下将一些递归转换为循环。

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

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

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

^{我借用了 Dijkstra 的“编程学科”中的大锤类比。}

小开

问题:

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

回答:

因为有些算法很难迭代求解。尝试用递归和迭代的方法解决深度优先搜索。您将会得到这样的想法: 通过迭代解决 DFS 显然是困难的。

另一个值得尝试的好方法是: 尝试迭代地编写 Merge sort。这将花费您相当长的时间。

问题:

所有使用递归的地方都可以使用 for 循环，这样说对吗？

回答:

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

问题:

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

回答:

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

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

小开

我似乎记得我的计算机科学教授曾经说过，所有有递归解决方案的问题都有迭代解决方案。他说，递归解决方案通常比较慢，但是当它们比迭代解决方案更容易推理和编写代码时，就会经常使用它们。

但是，对于更高级的递归解决方案，我不认为它总是能够使用简单的 for循环来实现它们。

小开

最佳答案

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

有些优化，比如尾部呼叫优化尾部呼叫优化，可以使递归更快，但并不总是可行的，也不是所有语言都能实现。

使用递归的主要原因是

在许多情况下，当它模仿我们对问题的处理方法时，它更加直观
使用递归(或者在任何情况下都需要栈)更容易探索一些数据结构，比如树

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

小开

简短的回答是: 在几乎所有情况下，递归都更快，for 循环占用的内存更少。然而，通常有一些方法可以改变 for 循环或递归，使其运行得更快

小开

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

小开

大多数答案似乎假设 iterative = for loop。如果 for 循环是无限制的(啊啦C，您可以对循环计数器做任何您想做的事情) ，那么这是正确的。如果它是真的 for循环(比如在 Python 或大多数函数式语言中，您不能手动修改循环计数器) ，那么它就是没有正确的。

所有(可计算的)函数都可以递归地实现，也可以使用 while循环(或者条件跳转，它们基本上是相同的)来实现。如果您真的将自己限制在 for loops中，那么您将只获得这些函数的一个子集(如果基本操作合理的话，就是原始递归函数)。当然，它是一个相当大的子集，恰好包含了您在实践中可能遇到的每一个函数。

更重要的是，许多函数非常容易递归实现，而且非常难以迭代实现(手动管理调用堆栈不算)。

小开

与纯迭代方法相比，递归 + 记忆可以得到更有效的解决方案，例如: Http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

小开

要使用迭代编写等价的方法，我们必须显式地使用堆栈。迭代版本的解决方案需要一个堆栈，这一事实表明该问题足够困难，可以从递归中获益。作为一般规则，递归最适合于不能用固定数量的内存解决的问题，因此在迭代解决时需要堆栈。尽管如此，递归和迭代可以在遵循不同模式的情况下显示相同的结果。要决定哪种方法更好地工作是逐个案例的，最佳实践是根据问题遵循的模式进行选择。

举例来说，要找出三角序列: 1361015..。使用迭代算法找到第 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));
}
}

小开

是的，作为说由 Thanakron Tandavas,

当你在解决一个可以用分而治之的技术来解决的问题时，递归是好的。

例如: 河内塔

N 环尺寸增大
三根杆子
环开始堆积在杆1。目标是移动环这样它们堆在三号杆上，但是
- 一次只能移动一个环。
- 不能把大戒指放在小戒指上面。
迭代解决方案是“强大而丑陋的”; 递归解决方案是“优雅的”。

递归与迭代

问题:

回答:

问题:

回答:

问题:

回答: