java - 递归和循环哪个更有效？

Question

我很好奇哪个迭代效率更高。我正在使用一个将字符串解析为列表。递归或循环是否更能提高 CPU 效率？内存效率更高吗？我所说的循环是指 for、foreach、do while、while 以及任何其他类型。在这些循环之外，哪个更有效率？或者说他们都是平等的？只是好奇。

Answer 1

您无法对此做出一般性声明。这取决于循环正在做什么、如何对其进行编码……以及 JIT 编译器对其进行优化的能力如何。它还可以对循环迭代的列表类型产生影响。递归也是如此。

为了获得可靠的答案，您需要根据具体情况检查各种替代方案，并(仔细!)在您的 Java 平台上对特定示例进行基准测试。

Java中的递归存在一个问题，即每一级递归都需要一个堆栈帧，而Java堆栈的大小是有限的。如果您必须递归得太深，您的算法将因 StackOverflowError 崩溃。 (当前一代 Java 平台没有实现尾部调用优化。)

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

<小时/>

幸运的是，不同类型的 Java 循环的性能差异通常不会产生足够的影响。因此(以堆栈深度问题为模，以及选择正确的 List 类的问题)，您可以安全地将性能留给“稍后”......并处理它如果且仅- 如果有必要进行性能优化。