迭代比递归快，还是不太容易发生堆栈溢出? [英] Is iteration faster than recursion, or just less prone to stack overflows?

问题描述

我知道您可以使用一个简单的循环来重写递归函数，方法是将数组用作剩余工作"的先进先出队列.我听说这降低了堆栈溢出的可能性.

I know you can rewrite a recursive function using a simple loop by using an array as a first-in-first-out queue of 'work remaining to be done'. I have heard this makes it less likely to have a stack overflow.

但是，如果堆栈溢出不是问题(因为您没有非常深入地递归)，是否有任何理由更喜欢迭代而不是递归?是不是更快了?

But if stack overflows aren't an issue (because you're not recursing very deeply), is there any reason to prefer iterative over recursive? Is it any faster?

我对 V8 上的 JavaScript 最感兴趣.

I'm mostly interested in JavaScript on V8.

推荐答案

在 Javascript 中，不做尾递归优化(不是必需的，也许不能?看评论)，递归是两者比迭代慢(因为在几乎所有语言中，函数调用都比跳转更昂贵)并且如果递归太深可能会导致堆栈溢出错误(但是，限制可以是相当深；Chrome 在我的实验中放弃了递归深度 16,316).

In Javascript, which doesn't (isn't required to, and perhaps can't? see the comments) do tail-recursion optimisation, recursion is both slower than iteration (because, in almost every language, a function call is much more expensive than a jump) and has the possibility of causing stack overflow errors if you recurse too deeply (however, the limit can be quite deep; Chrome gave up at recursion depth 16,316 in my experiment).

然而，当你编写递归函数时，性能影响有时值得你得到清晰的代码，而且如果没有递归，某些事情会变得更加困难(递归函数几乎总是很多 比它们的迭代对应物短)，例如使用树(但无论如何你并没有真正使用 Javascript 来做这件事 GGG 提到 DOM 是一棵树，并且在 JS 中使用它很常见).

However, the performance impact is sometimes worth the clarity of the code you get when you write a recursive function, and certain things are a lot more difficult to do without recursion (recursive functions are almost always much shorter than their iterative counterparts), e.g. working with trees (but you don't really do that with Javascript much anyway GGG mentioned that the DOM is a tree, and working with that is very common in JS).

这篇关于迭代比递归快，还是不太容易发生堆栈溢出?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！