Search code examples
javascriptrecursioniterationstack-overflow

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?

I'm mostly interested in JavaScript on V8.


Solution

  • 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).

    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 Edit: GGG mentioned that the DOM is a tree, and working with that is very common in JS).