24

有什么区别iteration，recursion为什么/什么时候更好：

while (true) {
    // Iterating
}

和

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

    return;
}

我看到了很多recursive实现，而它可以在一个简单的循环中轻松完成。

4

8 回答 8

36

递归和同一算法的迭代版本之间有两个主要区别。

首先，有时理解递归算法几乎比理解迭代算法更好（至少如果你是经验丰富的程序员）所以它确实增加了表达性和在某些情况下的可读性（在其他情况下也可能导致完全相反)

表达能力对编程语言来说是一笔巨大的交易，能够用 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

于 2013-11-05T17:19:37.570 回答
4

递归和迭代之间的主要区别在于内存使用。

对于每个递归调用都需要堆栈帧上的空间，从而导致内存开销。

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

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

所以最好让你的迭代代码比使用递归更容易理解。

于 2014-10-08T15:59:10.303 回答
1

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

于 2013-11-05T17:14:49.177 回答
0

递归和迭代是思考解决方案的不同方式。很难深入解释整个范围的差异。在您的示例代码中，您已经展示了差异。递归函数是调用自身的函数，而迭代函数是循环某个代码块的函数。这里有一些文章可以帮助您更好地理解它们： Recursion wiki

迭代维基

代码项目 SO #1

所以 #2

于 2013-11-05T17:20:04.487 回答
0

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

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

于 2013-11-05T17:20:54.353 回答
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;
}

IMO 之间唯一真正的区别是编译差异。

于 2013-11-05T17:21:44.527 回答
0

理论上，您总是可以在迭代和递归之间交换。但是，至少在 C/C++/C#/Java 的情况下，编译器会为您提供一些支持，这可能会使解决方案更加优雅，尤其是当您之前不知道循环数时。

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

于 2015-08-25T10:14:16.043 回答
-3

递归和迭代的区别

递归

  1. 递归函数 – 是一个由自身部分定义的函数
  2. 递归使用选择结构
  3. 如果递归步骤没有以收敛于某种条件（基本情况）的方式减少问题，则会发生无限递归
  4. 识别基本案例时递归终止
  5. 由于维护堆栈的开销，递归通常比迭代慢
  6. 递归比迭代使用更多的内存
  7. 无限递归会导致系统崩溃
  8. 递归使代码更小

迭代

  1. 迭代指令——基于循环的过程重复
  2. 迭代使用重复结构
  3. 如果循环条件测试永远不会变为假，则迭代会发生无限循环
  4. 当循环条件失败时迭代终止
  5. 迭代不使用堆栈，因此它比递归更快
  6. 迭代消耗更少的内存
  7. 无限循环重复使用 CPU 周期
  8. 迭代使代码更长

数据取自这里。

于 2016-02-19T08:07:28.750 回答