迭代比递归更快，还是更不容易出现堆栈溢出？ [英] 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屋！