2

我很好奇哪个对迭代更有效。我正在使用一个将字符串解析为列表。递归是更高效还是循环？内存效率更高吗？通过循环，我指的是 for、for each、do while、while 和任何其他类型。在这些循环中哪个更有效？还是他们都一样？只是好奇。

4

7 回答 7

8

你不能对此作出笼统的陈述。这取决于循环在做什么、如何编码……以及 JIT 编译器对其进行优化的能力如何。它还可以影响循环迭代的列表类型。递归也是如此。

要获得可靠的答案，您需要逐个检查各种替代方案，并（小心！）对 Java 平台上的特定示例进行基准测试。

Java 中的递归存在一个问题，即每一级递归都需要一个栈帧，而 Java 栈的大小是有界的。如果您必须递归太深，您的算法将崩溃并出现StackOverflowError. （当前一代 Java 平台不实现尾调用优化。）

您还希望避免在for i = 0 to size - 1a 上进行基于索引的迭代（例如）LinkedList，因为这会给您带来O(N^2)行为。

幸运的是，不同类型的 Java 循环的性能差异通常不会产生足够的影响。因此（以堆栈深度问题和选择正确List类的问题为模），您可以放心地将性能留给“以后”……并且仅在有必要进行性能优化时才处理它。

于 2013-09-15T01:55:18.100 回答
2

迭代通常会更有效。递归需要更多内存（设置堆栈帧）和时间（同样）。但是，如果您可以设置尾递归，编译器几乎肯定会将其编译为迭代或类似的东西，从而为您提供递归的可读性优势，以及迭代方法的性能。

在某些情况下，迭代解决方案将通过本质上维护您自己的堆栈来实现，因此差异可能很小。

请参阅递归是否比循环快？更多细节。

于 2013-09-15T01:53:33.343 回答
1

好吧，根据我的说法，对您的问题的最佳答案是“视情况而定”：

平均而言，在 SORTED 集合中搜索时，递归要快得多，因为您可以使用诸如“分而治之”之类的算法（在这种情况下，将集合分成两部分并将元素可能所在的一半发送到递归的下一步. 当元素被找到或不包含在集合中时，递归停止）。

但在大多数情况下，循环比递归更有效，因为在不同级别的递归中下降时，CPU 将变量保存在堆栈中，这基本上将其填满。循环仅在堆栈中使用恒定数量的空间（通常，但有例外）。例如，如果您使用递归算法计算斐波那契数列，则在斐波那契（30）之后需要数年才能得到结果。该序列可以通过记忆（基本上使用循环）来计算。

要记住的一件事是，递归比循环更容易理解并且更容易帮助解决问题。许多基于循环的问题解决方案都是从递归算法（分治法）开始的，该算法在循环算法（记忆化）中得到优化。我上了一堂关于这个主题的课，真的很有趣。

希望我有所帮助。

问候。

于 2013-09-15T02:06:33.570 回答
0

某些情况更适合递归……而其他情况更适合简单迭代。例如，导航目录优于递归。其他树结构也一样。但是递归使用更多的内存。对于迭代简单列表（如字符串），迭代（循环）更有效。

于 2013-09-15T01:53:40.663 回答
0

在我的选择中，循环更好，递归会有函数调用跟踪，这会占用更多的内存。再次取决于功能

于 2013-09-15T02:26:52.113 回答
0

我同意其他海报，因为这实际上取决于您要解决的问题。我个人的偏好是通常避免递归，因为与迭代相比，它可能更难以维护和调试，并且取决于实现者或维护者的技能（谁是较弱的环节）。然而，没有提到的一项是使用一些新的 Java 线程特性（例如 ForkJoinPool），可以很容易地将递归解决方案变成多线程解决方案。并不是说 Java 中的线程很困难，但是如果在线程中分配工作负载成为一个问题并且这种类型的功能很有用，那么在设计系统时需要考虑这一点。

于 2013-09-15T02:43:49.483 回答
0

我创建了两个衡量递归与循环性能的微基准。他们都在随机数据集上执行计算，以避免 JIT 作弊。

在第一种情况下，我计算随机整数矩阵中单元格的总和。当矩阵的一侧等于 60 时，递归比循环慢 10 倍。

在第二种情况下，我通过生成斐波那契数来比较递归与递归仿真。递归仿真是 GC 友好的 - 计算期间没有内存分配。在这种情况下，递归在“较小”情况下快 2 倍，在繁重计算下快 5 倍。

所以底线是Java中的递归非常有效，尽管不像循环那样有效。

Environment:
OS: Windows 8 6.2, Core i5
JVM: Oracle Corporation Java HotSpot(TM) 64-Bit Server VM 23.25-b01

可在github获得源代码。

于 2013-09-21T21:22:11.217 回答