迭代比递归更快，还是只是不容易出现堆栈溢出的问题？

Question

我知道你可以使用数组作为先进先出的队列来重写递归函数，从而使用简单循环。我听说这样做可以减少堆栈溢出的可能性。

但是如果堆栈溢出不是问题（因为你没有深度递归），是否有理由更喜欢迭代而不是递归？它会更快吗？

我主要关注V8上的JavaScript。

- callum

---

你可以尝试进行基准测试。如果它是一个小数组，我会选择最易读的解决方案。 - Zeta Two

Answer 1

在Javascript中，递归比迭代慢（因为在几乎所有语言中，函数调用比跳转要昂贵得多），并且如果递归深度太深会导致堆栈溢出错误（然而，限制可以非常深; Chrome在我的实验中放弃了递归深度16,316） 。然而，有时性能影响是值得的，因为递归函数可以获得更清晰的代码，并且某些事情没有递归将更加困难（递归函数几乎总是比它们的迭代对应物短），例如操作树形结构（但你实际上不会在Javascript中经常这样做编辑： GGG提到DOM是一棵树，使用它非常常见）。

- Seth Carnegie

---

很棒的答案，解释了选择递归或迭代实现时需要考虑的所有因素。+1 提到了可维护性。 - Andy

最近有一个问题提出了一个有趣的观点，即（非标准的）Function#arguments这样的存在意味着现实世界中的JS引擎无法执行尾递归消除...我假设他们否则会这样做，无论是否需要。 - Dagg Nabbit

我会尽力进行翻译，并在保持原意的前提下使内容更加通俗易懂。以下是需要翻译的内容：另外，我认为DOM可以看作是一棵树，在JS中经常与DOM打交道......而且，写得好的迭代代码可以比递归代码更短，并且在可读性方面也相当...也许我应该发布一个答案，在评论中发牢骚很抱歉;) - Dagg Nabbit

@GGG，不完全是这样。更多的是出于安全考虑。Mark Miller和我为SES推动了这一点。启用某些其他优化只是帮助他们更容易接受。 - Mike Samuel

@MikeSamuel 很有趣，我不知道...感谢你指出来。 - Dagg Nabbit

Answer 2

递归可能会更快地失败，因为无限递归函数将会耗尽堆栈并产生异常，程序可以从异常中恢复，而迭代解决方案将一直运行直到被外部代理停止。

对于需要时间生成有效输出的代码，递归的主要成本是函数调用开销。迭代解决方案根本没有这个问题，因此在不显式优化递归的语言中，往往在性能关键代码中胜出。

在基准测试中确实很明显，但除非你正在编写性能关键代码，否则你的用户可能不会注意到。

http://jsperf.com/function-call-overhead-test上的基准测试试图量化各种JS解释器中的函数调用开销。如果您担心，可以组合一个类似的基准测试来明确测试递归。

---

请注意，在EcmaScript 3中正确执行尾递归优化很困难。

例如，在JavaScript中实现简单的数组折叠：

function fold(f, x, i, arr) {
  if (i === arr.length) { return x; }
  var nextX = f(x, arr[i]);
  return fold(f, nextX, i+1, arr);
}

由于调用，无法进行尾部优化

 fold(eval, 'var fold=alert', 0, [0])

在 fold 的正文中执行 eval('var fold=alert') 会导致表面上的尾调用 fold 不实际进行递归。

EcmaScript 5 更改了 eval 的调用方式，使其除了通过名称 eval 调用外不可被调用，并且严格模式阻止 eval 引入局部变量，但是尾调用优化取决于静态确定尾调用位置的能力，在像 JavaScript 这样的动态语言中并不总是可能。

- Mike Samuel

Answer 3

我对以下比较结果感到惊讶，你可以看到它们之间的差异。通常情况下，迭代更快，但是如果你需要执行大量递归操作，则差异可能会很大。

function factorialRec(n){
  if (n > 0) {
    return n * factorialRec(n - 1)
  } else {
    return 1;
  }
}

function factorial(n){
  var returnme = n;
  for(var i = n - 1; i > 0; i--){
    returnme *= i;
  }
  return returnme;
}

console.time('recursion')
for(var i=0;i<1000000;i++){
  factorialRec(100);
}
console.timeEnd('recursion')

console.time('iteration')
for(var i=0;i<1000000;i++){
  factorial(100);
}
console.timeEnd('iteration')

注意：虽然上面的示例非常有说服力，但实际上，您不应该遇到这么多的函数调用。因此，大多数情况下，减速不应与此问题有关。

- windmaomao

Answer 4

这取决于情况... 当我在递归函数中遇到“脚本缓慢”错误时，我也问了同样的问题。令人惊讶的是，迭代实际上更慢。我正在遍历树以搜索特定节点。我已经使用类似的方法将递归函数重写为迭代方式（使用堆栈来保持上下文）：https://dev59.com/ZHVC5IYBdhLWcg3w21Mq#159777 然而，之后我开始在IE 8中收到比以前更多的“脚本缓慢”错误。进行一些分析确认迭代版本甚至更慢。这个原因可能是在JS中使用方法调用栈可能比在循环内使用具有相应push()和pop()操作的数组更快。为了验证这一点，我创建了一个测试，模拟两种情况下的树遍历：http://jsperf.com/recursion-vs-iteration-852结果令人惊讶。虽然在Chrome中，迭代版本（在我的情况下）比递归版本慢19％，但在IE 8中，迭代版本比递归版本慢65％。

- petrsyn

---

我也发现迭代实现并不总是更快。 - Steven Keith

尝试通过预先分配数组并通过跟踪当前索引来维护栈。我敢打赌这比 push/pop 快得多。例如 var stack = new Array(size); var stack_index = 0; - SapphireSun

啊，没错，IE8，我们都用它来运行我们最新和最易读的递归代码。 - Jaacko Torus

也许检查回答的时间会更好。那是在2013年... - petrsyn