34

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

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

4

8 回答 8

41

递归方法总是比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越大。

于 2013-03-11T19:24:29.307 回答
10

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

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

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

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

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

于 2013-03-11T19:27:12.830 回答
8

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

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

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

递归分为三种类型，具体取决于它们如何直接转换为迭代：

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

严格来说，递归和迭代都同样强大。任何递归解决方案都可以实现为带有堆栈的迭代解决方案。逆变换可能比较棘手，但最简单的就是通过调用链将状态向下传递。

在 Java 中，有一种情况是递归解决方案优于（幼稚的）迭代解决方案，另一种情况是它们基本上是等价的。在大多数其他情况下，迭代解决方案会更好，因为避免了函数调用开销。

如果函数隐式使用堆栈，则递归解决方案通常会更好。考虑深度优先搜索：

void walkTree(TreeNode t) {
    doSomething(t);

    if (t.hasLeft()) { walkTree(t.getLeft()); }
    if (t.hasRight()) { walkTree(t.getRight()); }
}

与等效的迭代解决方案相比

void walkTree(TreeNode t) {
    Stack<TreeNode> s = new Stack<TreeNode>();
    s.push(t);
    while (!s.empty()) {
        TreeNode t = s.pop();
        doSomething(t);
        if (t.hasLeft()) { s.push(t.getLeft()); }
        if (t.hasRight()) { s.push(t.getRight()); }
    }
}

在迭代的情况下，您将不得不为Stack<>对象创建的任何垃圾付费。在递归的情况下，您将使用进程堆栈，它不会产生任何垃圾或分配任何内存。递归解决方案容易受到堆栈溢出的影响，但否则会运行得更快。

如果函数使用尾递归，那么这两个解决方案将是等价的，因为 JIT 会将递归解决方案转换为迭代解决方案。尾递归是函数做的最后一件事是递归调用自身，允许编译器忽略任何累积的状态。比如遍历一个列表

void walkList(ListNode n) {
    doSomething(n);
    if (n.hasNext()) { walkList(n.getNext()); }
}

由于“walkList”是函数中完成的最后一件事，JIT 会将其本质上转换为“n = n.getNext(); goto beginning”，这将使其等同于迭代解决方案。

在大多数其他情况下，迭代解决方案会更好。例如，如果您想进行广度优先搜索，那么您可以在迭代解决方案中使用 aQueue而不是 a Stack，并使其立即工作，而将其转换为递归解决方案则需要您为两个隐式堆栈付费调用堆栈，并且仍然为队列付费。

于 2013-03-11T19:55:28.553 回答
0

你是什​​么意思更好？每个递归也可以通过迭代来实现，反之亦然。有时递归更容易理解。然而，由于递归会使堆栈膨胀，许多嵌套调用可能会导致内存不足异常。在这种情况下，递归显然不是您的最佳选择。

于 2013-03-11T19:23:13.460 回答
0

“递归总是比迭代好”这句话是错误的。在某些情况下，任何一个都比另一个更可取。

很难就使用哪种类型的算法给你一个决定性的答案，因为它取决于特定情况。例如，斐波那契数列的常见教科书递归案例使用递归非常低效，因此在这种情况下最好使用迭代。相反，使用递归可以更有效地实现遍历树。

要回答您的第二个问题，是的，任何迭代算法都可以使用递归来实现，反之亦然。

于 2013-03-11T19:32:19.380 回答
0

通常递归方法需要几行代码，但需要对您的算法进行深入思考。如果你犯了一个逻辑错误，你可能会得到一个StackOverflowError.

下面是阶乘的 2 个编程示例：

迭代：

public int calculateIteractiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    int factorial = 1;
    for (int i = 1; i <= n; i++) {
        factorial = factorial * i;
    }
    return factorial;
}

递归：

public int calculateRecursiveFactorial(int n) {
    // Base case
    if (n == 1) {
        return 1;
    }
    return n * calculateRecursiveFactorial(n - 1);
}

为每个提案反映不同的想法总是好的，总是考虑代码行数、复杂性、清晰度、凝聚力等。

于 2013-03-11T19:46:40.297 回答
0

如果我们还记得 java 的按值传递机制，我们可以理解递归消耗更多内存，因为每次调用都传递对象引用地址的副本或某些原始类型的值。因此，作为您为每个递归调用传递的马赫参数，作为您将为每个调用消耗的马赫内存，另一方面，循环使用起来很轻松。但是我们当然知道有“分而治之”的算法，例如合并排序或树上的迭代，它们在递归的帮助下消耗更少的步骤来给出结果。所以在这些情况下，我认为最好使用递归。

于 2013-03-11T20:40:38.523 回答