递归与迭代的比较

Question

在任何使用递归的地方都可以使用for循环吗？如果递归通常比for循环慢，那么为什么要使用它而不是for循环迭代呢？

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

- Breako Breako

---

“递归”与“迭代”？我认为“迭代”等同于“for循环”。 - gongzhitaao

Tom Moertel的博客有四篇关于将递归代码转换为迭代代码的优秀文章：http://blog.moertel.com/tags/recursion.html - cjohnson318

Answer 1

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

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

使用递归的主要原因是

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

当然，每个递归可以被建模为某种循环：这就是CPU最终要做的。 而递归本身，更直接地说，意味着将函数调用和作用域放入堆栈中。 但将您的递归算法更改为循环算法可能需要大量工作，并使您的代码难以维护：对于每个优化，应仅在某些 profiling 或证据显示其必要性时尝试。

- Denys Séguret

---

此外，递归与“缩减”这个术语密切相关，在许多算法和计算机科学中都扮演着核心角色。 - SomeWittyUsername

请问您能否提供一个递归使代码更易维护的例子？根据我的经验，通常情况是相反的。谢谢。 - Yeikel

@Yeikel 写一个函数 f(n)，它返回第n个 斐波那契数。 - Matt

Answer 2

每次使用递归时，都可以用for循环吗？

是的，因为在大多数CPU中，递归是通过循环和堆栈数据结构进行建模的。

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

并不是“通常比较慢”，而是应用不正确的递归才会比较慢。此外，现代编译器善于将一些递归转换为循环，甚至不需要提前请求。

如果总是能够将递归转换为for循环，那么是否有经验法则来实现这一点？

对于最好迭代解释的算法，请编写迭代程序；对于最好递归解释的算法，请编写递归程序。

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

---

⁺我从Dijkstra的“编程学科”中借用了这个比喻。

- Sergey Kalinichenko

---

递归通常会更加耗费资源（速度慢/内存占用大），因为需要创建堆栈帧等东西。当适用于足够复杂的问题时，差异可能很小，但仍然更昂贵。但有可能存在尾部递归优化等例外情况。 - Bernhard Barker

我不确定在每种情况下都只需要一个for循环。请考虑更复杂的递归或具有多个变量的递归。 - SomeWittyUsername

@icepack 是的，这是可能的。虽然可能不太美观，但是它是可行的。 - Bernhard Barker

我不确定我同意你的第一句话。CPU本身并没有真正地模拟递归，而是在CPU上运行的指令模拟递归。其次，循环结构并没有（必然）具有动态增长和缩小的数据集，而递归算法通常会为每个递归深度步进时产生一个数据集。 - trumpetlicks

你可以将调用栈视为最初的自动内存管理。几乎所有需要单个栈的算法都可以自然地映射到递归实现中，而任何非递归实现都需要手动实现和管理栈... - comingstorm

Answer 3

问题：

如果递归通常比循环迭代慢，那么为什么要使用它而不是循环迭代？

答案：

因为一些算法难以通过迭代解决。尝试递归和迭代地解决深度优先搜索。你会发现用迭代求解DFS非常困难。

另一个好的尝试：尝试用迭代方式编写归并排序。这需要花费相当长的时间。

问题：

是否可以说在所有使用递归的地方都可以使用for循环？

答案：

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

问题：

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

答案：

相信我，尝试自己编写迭代式深度优先搜索的版本。你会发现一些问题递归求解更容易。

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

- Thanakron Tandavas

---

我欣赏你试图提供权威的答案，并且相信作者很聪明，但“相信我”并不是对一个有意义的问题的有益回答，因为这个问题的答案并不是显而易见的。有非常直观的算法来执行迭代深度优先搜索。请参考此页面底部的示例，其中包含伪代码描述算法的详细信息：http://www.csl.mtu.edu/cs2321/www/newLectures/26_Depth_First_Search.html - jdelman

Answer 4

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

- G. Steigert

Answer 5

要使用迭代来编写等效的方法，我们必须明确地使用一个栈。迭代版本需要使用栈来解决问题，这表明该问题足够复杂，可以从递归中受益。一般而言，递归最适合无法使用固定内存解决并因此在迭代解决时需要使用栈的问题。

话虽如此，递归和迭代可以展现相同的结果，但它们遵循不同的模式。决定哪种方法更好是根据具体情况而定，最佳实践是选择基于问题遵循的模式。

例如，要找到第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)); 
   }
}

- shirin

Answer 6

正如Thanakron Tandavas所said，递归在解决可以通过分治技术解决的问题时很有用。

例如：汉诺塔

条件如下：

1. N个不断增大的圆盘
2. 3根柱子
3. 圆盘从一开始就堆叠在第1个柱子上。目标是将圆盘移动到柱子3上...但是
   • 一次只能移动一个圆盘。
   • 不能将较大的圆盘放在较小的圆盘上面。
4. 迭代解法“强大但难看”；递归解法“优美”。

- Ramesh Mukkera

---

一个有趣的例子。我猜你知道M.C. Er的论文《汉诺塔和二进制数》。这个论文也在3brown1blue的精彩视频中得到了介绍。 - Andrestand

Answer 7

我记得我的计算机科学教授曾经说过，所有具有递归解决方案的问题也都有迭代解决方案。他说递归解决方案通常较慢，但在易于推理和编码时，它们经常被使用。

然而，在更高级的递归解决方案中，我不认为总是能够使用简单的for循环来实现。

- Vivian River

---

将递归算法转换为迭代算法（使用堆栈）始终是可能的。您可能不会得到特别简单的循环，但这是可能的。 - Bernhard Barker

Answer 8

大多数答案似乎假定 iterative = for loop。如果您的for loop未受限制 (a la C，可以对循环计数器进行任何操作)，那么这是正确的。如果它是一个真正的 for 循环(例如Python或大多数函数语言中无法手动修改循环计数器)，那么就不正确。

所有（可计算）函数都可以递归地实现，并使用 while 循环 (或条件跳转，基本上是相同的东西)。如果你真的仅限于使用 for loops，那么你只会得到其中的一个子集(原始递归函数，如果你的基本运算是合理的)。毫无疑问，这是一个相当大的子集，包含了你在实践中可能遇到的每一个函数。

更重要的是，许多函数在递归实现时非常容易实现，在迭代实现时则非常困难(手动管理调用堆栈是无效的)。

- Jbeuh

Answer 9

使用递归加上记忆化可能会比纯迭代方法更有效率，例如查看此链接： http://jsperf.com/fibonacci-memoized-vs-iterative-for-large-n

- Reza Afzalan

---

任何递归代码都可以使用堆栈转换为功能上相同的迭代代码。你展示的差异是解决相同问题的两种方法之间的差异，而不是递归和迭代之间的差异。 - Bernhard Barker

Answer 10

简短回答：在大多数情况下，循环比递归占用更少的内存，但递归更快。然而，通常有方法可以改变循环或递归以使其运行更快。

- Jessica Shu