How to flatten out deeply nested recursion to prevent stack overflow on IE8

IE8 only allows your execution stack to be like 30-100 function calls, which basically prevents taking advantage of recursion. Some examples where you use a lot of recursion include building recursive descent parsers, or even more simple cases such as executing tests recursively:

https://github.com/visionmedia/mocha/issues/502

Below I compare two ways of accomplishing the same thing, one using the much simpler version that uses recursion (but breaks on <=IE8 when recursion is too deep), and the more obtuse but <=IE8 compatible version.

Recursive structure

function a(n) {
  return b(n + 1) + b(n + 2) + b(n + 3);
}

function b(n) {
  return n + c(n);
}

function c(n) {
  return n + n;
}

function parse(n) {
  return a(n);
}

Executing the function gives 18:

console.log(parse(0)); // 18

If you throw an error in c and inspect the stack, you'll see that it includes a and b since it's recursive:

/**
 * Error
    at c (./recursion.js:11:15)
    at b (./recursion.js:7:14)
    at a (./recursion.js:3:32)
    at parse (./recursion.js:16:10)
 */

function c(n) {
  try { throw new Error } catch (e) { console.log(e.stack) }
  return n + n;
}

This is a problem for <= IE8, where it only allows a very shallow execution stack (just a few hundred function calls, whereas modern JS engines seem to allow thousands). Here is an example:

https://github.com/visionmedia/mocha/issues/502

In the case you end up using recursion, such as for the tower expression parser (a recursive descent parser basically), this can become a problem in IE8 and below. You can fix this by flattening out the recursion:

function a(n, stack) {
  stack.push([b, n + 1]);
  stack.push([b, n + 2]);
  stack.push([b, n + 3]);
}

function b(n, stack) {
  stack.push([identity, n]);
  stack.push([c, n]);
}

function c(n, stack) {
  stack.push([identity, n + n]);
}

function identity(val) {
  return val;
}

function parse(n) {
  var stack = [];
  // push initial functions into stack
  a(n, stack);

  var result = 0;

  while (stack.length) {
    var fn = stack.shift();
    var val = fn[0].apply(null, [fn[1], stack]);
    if (val) result += val;
  }

  return result;
}

console.log(parse(0));

Now if you inspect the stack at c, it is shallow:

/**
 * Error
    at C (./recursion.js:47:15)
    at Parse (./recursion.js:64:21)
 */

function c(n, stack) {
  try { throw new Error } catch (e) { console.log(e.stack) }
  stack.push([identity, n + n]);
}

This approach is definitely not as pretty, nor as easy to understand, as the recursive version, but it does solve the problem of having too deep a stack trace for incompetent browsers. Hopefully, though, IE8 will be phased out and we can move on :)

Another solution would be to use setImmediate and create an async API. But for our particular use case, making a client-side template renderer async would just slow down rendering, and that's something I want to avoid.

Do you know of a better way to accomplish this?