迭代和递归有什么区别？

Question

迭代和递归有什么区别？

24

迭代（iteration）和递归（recursion）有何区别，为什么或者何时使用一种更好：

while (true) {
    // Iterating
}

并且

private void recursion() {
    if (true)
        recursion(); // Recursing

    return;
}

我看到很多使用递归实现的代码，而这些代码其实可以用一个简单的循环来实现。

- user2742371

1

函数式语言倾向于鼓励递归。在 C 语言中不太常见，但仍然非常有用、强大且对某些问题必需。迭代通常更快，一些编译器实际上会将某些递归代码转换为迭代。递归通常比迭代更优雅。 - Charlie Burns

可能是递归还是迭代？的重复问题。 - Alexander Shukaev

作者，请学会使用谷歌和在SO上搜索。这个问题必须关闭并删除，因为已经有101个重复的问题了。我已经看到了大量的复制/粘贴答案。 - Alexander Shukaev

@Haroogan 在我提问之前，我确实搜索过了，但那些答案对我来说并不够用，直到现在我才明白。 - user2742371

8个回答

4

递归和迭代的主要区别在于内存使用。每次递归调用都需要在堆栈帧上分配空间，从而造成内存开销。

让我举个例子。想象一下，在某种情况下，你忘记为递归函数编写基本情况，导致无限递归调用，在另一种情况下，你编写了一个无限循环。

由于每个递归函数都会分配新的内存空间，在第一种情况下，你的代码会出现堆栈溢出异常，但在第二种情况下，它将一直运行下去。

因此，最好使你的迭代代码更易理解，而不是使用递归。

- mohit verma

1

非常正确，从没想过，加一！ - user2742371

1

内存使用情况并不简单，因为尾调用优化现在相当普遍。许多递归算法自然地包含像 return recurse(arg) 这样的行，其他算法可以轻松重写以使用此形式。这样做时，返回路径只是爬升堆栈每次返回。您可以通过仅对第一个函数调用不使用堆栈 - 立即返回并且不为每个递归使用任何额外的内存来优化此过程。 - lod

1

他们是完成同一件事情的不同方法。所有递归实现都可以使用一个（或多个）循环来完成，反之亦然。更重要的是其背后的逻辑，一种思考方式。阶乘虽然不是最好的例子，但它是n * (n-1)！，因此递归使用它是有意义的。

- clcto

0

理论上，您总是可以在迭代和递归之间进行切换。然而，在C/C++/C#/Java的情况下，编译器为您提供了一些支持，这可能会使解决方案更加优雅，特别是当您不知道循环次数时。

最好的例子是列出文件夹及其子文件夹中的所有文件。如果有几个包含子文件夹的子文件夹，则通常在迭代模式下，您需要一个堆栈来保存所有需要分析的文件夹。在递归方法的情况下，堆栈已经由编译器提供，解决方案更加优雅。

- AndreiM

0

递归和迭代是思考解决方案的不同方式。在完整范围内深入解释这两者的区别可能会有些困难。在您的示例代码中，您已经展示了它们之间的差异。

递归函数是调用自身的函数，而迭代函数则是循环执行某个代码块。以下是一些文章，可以帮助您更好地理解它们：

- Roman

0

它们可以交替使用来解决不同的问题。本质上，您可以将递归函数迭代地编写，反之亦然。

迭代可能会提高程序的性能。而递归可能会给出更直观和优雅的结果。您可以根据自己的偏好选择其中任何一种！

- Montaldo

0

递归函数通过调用自身的过程工作，直到满足条件，而迭代则使用循环控制结构（例如while、do while、for）以重复一段代码，直到满足某个条件为止。

递归示例：

int rec_func(int u, int k) {
  if (k == 0)
    return u;
  return rec_func(u * k, k - 1);
}

迭代示例：

int ite_func(int u, int k) {
  while (k != 0) {
    u = u * k;
    k = k - 1;
  }
  return u;
}

在我看来，它们之间唯一真正的区别是编译差异。

- CopyAndPaste

不，不是真的。在上面的代码示例中，一个会无限循环，而另一个则会在堆栈已满时导致错误。 - clcto

-3

递归和迭代之间的区别

递归

递归函数 - 是一种部分由自身定义的函数
递归使用选择结构
如果递归步骤不能以收敛于某些条件（基本情况）的方式减少问题，则会发生无限递归
当识别到基本情况时，递归终止
由于需要维护堆栈的开销，递归通常比迭代慢
递归使用的内存比迭代更多
无限递归可能会导致系统崩溃
递归使代码更小

迭代

迭代指令 - 是基于循环的过程重复
迭代使用重复结构
如果循环条件测试永远不为假，则会出现无限循环
当循环条件失败时，迭代终止
迭代不使用堆栈，因此比递归快
迭代消耗的内存较少
无限循环会反复使用CPU周期
迭代使代码更长

数据取自这里。

- Yasir

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- iordanis · Accepted Answer

有两个主要区别，递归和相同算法的迭代版本。首先，有时候理解递归算法比迭代算法更好（至少对于有经验的程序员来说），因此它增加了表达能力，在某些情况下也增加了可读性（在其他情况下可能会导致完全相反的结果）。表达能力在编程语言中非常重要，能够用5行代码而不是20行代码编写相同的代码非常重要。但是，递归算法会降低代码的性能。递归函数必须将函数记录保存在内存中，并跳转到另一个内存地址以被调用以传递参数和返回值。这使得它们在性能方面非常糟糕。总结一下：迭代算法=快速执行但难以编写（有时也难以阅读）；递归算法=编写快速但性能差（有时更容易理解）。以这个例子为例：

public static long fib(long n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

对比

    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        long prev = 1, current = 1, next = 0;
        for (long i = 3; i <= n; i++) {
            next = prev + current;
            prev = current;
            current = next;
        }
        return next;
    }

来源：

http://www.csd.uwo.ca/Courses/CS1027a/code/FibonacciDemo.java