递归方法总是比 Java 中的迭代方法好吗？

Question

递归方法总是比 Java 中的迭代方法好吗？

也可以始终使用它们代替迭代，反之亦然吗？

原文由 Hoon 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

递归方法总是比 Java 中的迭代方法好吗？

不

也可以始终使用它们代替迭代，反之亦然吗？

您 始终 可以从递归函数创建迭代函数（如果内存可以处理它，请参见 此处 的有趣链接）。

对于某些情况，最好使用递归（比如处理树时……在二叉树上移动等）。对我来说，如果使用循环并不比递归复杂和困难得多，我更喜欢使用循环。

递归使用更多内存，但有时更清晰可读。 使用循环可以提高性能，但递归有时对程序员（以及他们的性能）更好。

所以，总而言之，决定使用什么 - 递归或迭代，取决于你想要实现什么，以及什么对你更重要（可读性，性能……），并且要求 递归或迭代 就像要求 优雅或性能.

---

例子

考虑 阶乘 的这两个实现：

迭代：

 private int Factorial(int num)
{
    int result = 1;
    if (num <= 1)
       return result;
    while (num > 1)
    {
        result * = num;
        num--;
    }
    return result;
}

递归：

 private int Factorial(int num)
{
    if (num <= 1)
        return 1;
    return num * Factorial(num - 1);
}

哪种方法 更具可读性？

显然是递归的，它是直接的，可以从第一次尝试编写并成功运行 - 它只是将数学定义翻译成 Java ！

哪种方法 效率更高？

以 num = 40 为例，这是一个 时间比较：

 long start = System.nanoTime();
int res = Factorial(40);
long end = System.nanoTime();
long elapsed = end - start;

System.out.println("Time: " + elapsed);

2993 为递归

2138 为迭代

当然， num 越大，差异越大。

原文由 Maroun 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

_递归有利于程序员理解程序，但很多时候它们会导致堆栈溢出，因此总是更喜欢迭代_。

事实上，递归很少是解决问题最有效的方法，而迭代几乎总是更有效。这是因为调用堆栈在递归期间被大量使用，因此通常有更多的开销与递归调用相关联。

这意味着许多计算机编程语言将花费更多时间来维护调用堆栈，然后它们将实际执行必要的计算。

递归是否比迭代使用更多的内存？ 一般来说，是的。这是因为调用堆栈的广泛使用。

我应该使用递归还是迭代？

通常使用递归，因为它实现起来更简单，而且通常比迭代解决方案更“优雅”。请记住，在递归中完成的任何事情也可以迭代地完成，但递归通常存在性能缺陷。但是，根据您试图解决的问题，性能缺陷可能非常微不足道——在这种情况下使用递归是有意义的。使用递归，您还可以获得其他程序员可以更轻松地理解您的代码的额外好处——这总是一件好事。

原文由 amod 发布，翻译遵循 CC BY-SA 3.0 许可协议