Is iteration faster than recursion, or just less prone to stack overflows?

Question

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.

Answer 1

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

Answer 2

Recursion may fail faster since an infinitely recursive function will blow out the stack producing an exception that the program can recover from, while an iterative solution will run until stopped by an outside agent.

For code that will produce a valid output given time, the main cost of recursion is function call overhead. Iterative solutions simply don't have this, so tend to win in performance critical code in languages that don't explicitly optimize for recursion.

It's definitely noticeable in benchmarks, but unless you're writing performance critical code, your users probably won't notice.

The benchmarks at http://jsperf.com/function-call-overhead-test try to quantify function call overhead in various JS interpreters. I would put together a similar benchmark that explicitly tests recursion if you're worried.

---

Note that tail-call recursion optimization is difficult to do correctly in EcmaScript 3.

For example, a simple implementation of array folding in 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);
}

cannot be tail-optimized because the call

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

would eval('var fold=alert') inside the body of fold, causing the seemingly tail-recursive call to fold to not be actually recursive.

EcmaScript 5 changed eval to not be callable except via the name eval, and strict mode prevents eval from introducing local variables, but tail-call optimization depends on the ability to statically determine where a tail-call goes which is not always possible in dynamic languages like JavaScript.

Answer 3

This depends... I was asking the same question when I was experiencing the "Slow script" error in IE8 in recursive function. And was surprised that iteration was actually even slower.

I was walking through a tree searching for a specific node. And I have rewritten my recursive function to iterative way (using stack to keep context) using the similar approach: https://stackoverflow.com/a/159777/1245231

After that I however started getting much more "Slow script" errors from IE 8 than before. Doing some profiling confirmed that the iterative version was even slower.

The reason for this can be that using method call stack in JS is probably faster than using array with corresponding push() and pop() operations within a loop. To verify this I've created test that simulates tree walking in both cases: http://jsperf.com/recursion-vs-iteration-852 The results are surprising. While in Chrome the iterative version is (in my case) 19% slower, in IE8 the iterative version is 65% slower than the recursive version.