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

Question

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

它们也可以用来代替迭代,反之亦然吗？

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更大时差异会更大.

Answer 2

更正其他答案：任何迭代都可以转换为递归（注意可能会发生堆栈溢出）。然而，并不是所有的递归都可以直接转化为迭代。通常，您需要某种形式的暂存空间来保存原本会存储在堆栈中的数据。

至于选择哪个：这取决于您的语言和编写递归解决方案的便利性。

编辑，澄清我所说的“直接”是什么意思：

根据递归转换为迭代的直接程度，共有三种类型的递归：

• 尾调用可优化，其中方法中的最后一个操作是递归调用。这些可以直接转换为循环。
• 不可尾调用优化的递归，因为它需要在调用之间保留信息，但不需要堆栈。一个阶乘表示为fact(N)经典示例：在递归公式中，最后一个操作不是递归调用，而是乘法。这些类型的递归调用可以很容易地转化为尾调用优化形式，进而转化为迭代形式（要将阶乘转化为尾调用优化形式，必须使用双参数版本fact(n, acc)，acc累加结果在哪里） .
• 需要在每次调用时保留状态的递归。经典示例是先序树遍历：在每次调用时，您必须记住父节点。没有办法将其直接转换为迭代。相反，您必须构建自己的堆栈来保存每次调用的状态。

Answer 3

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

事实上，递归很少是解决问题的最有效方法，而迭代几乎总是更有效。这是因为调用堆栈在递归过程中被大量使用，通常与进行递归调用相关的开销更多。
这意味着许多计算机编程语言将花费更多的时间来维护调用堆栈，然后它们将实际执行必要的计算。

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

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

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