Properly Biting Javascript's Tail

All code is editable with live results.

Recursion and TCO post-es2015

One—or maybe the most exiting feature of es2015—is tail call optimization or TCO.

Recursion can be problematic due to limitations on the call-stack size. Each time you call a function from within another function, the JavaScript engine remembers where you did the call. It does that for various reasons One way I like to think of it is the JS engine needs to remember the context your function runs in, especially local variables.

But since you have a limit to the amount of memory available on your machine, there is a limit to the call stack size and your theoretically valid JS code can crash because of this limit.

Let’s see an example with a function doing a recursive addition:


x
 
function addMe(n) {
  if (n < 1) {
    return 1;
  }
  return n + addMe(n-1);
}
addMe(1000000);
x
 
RangeError: Maximum call stack size exceeded

Now let’s make a TCO version of it. Our goal here is to give hints to the JS engine to detect that it can optimize our function into a TCO one. For the JS engine this optimization is seen as: oh cool I don’t need to remember the previous function call environment, so I will just reuse it for this new function call. JS engines can implement this forgetting part differently, what’s important is the call stack does not grow.

You need a recent browser for this to work, at the time I write this Safari and Canary support it


x
 
function addMeTCO(n) {
  "use strict";
  function __add(n, acc) {
    if (n < 1) {
      return acc;
    }
    return __add(n-1, acc + n);
  }
  return __add(n, 0);
}
addMeTCO(1000000);
x
 
RangeError: Maximum call stack size exceeded

There are two simple steps:

The first step is to use strict mode. Easy enough.
The second one is to make sure that in our return statements, no extra work is happening. We only want to return a function with some parameters. It means we went to something like n + addMe(n-1)—note the extra n + computation here— to __add(n, 1) and __add(n-1, acc + n).

I am now using an accumulator that I pass as a parameter to store my results. Another way to see it is I am using the arguments of my function calls to store the results instead of the extra addition after the function returns.

Yes I know what you are thinking, the function looks a little more complicated now. But it is now possible to use recursion everywhere in Javascript. It opens the possibility of an even more functional approach to Javascript and with this—and I am a strong believer of it—robustness comes.

Recursion and TCO pre-es2015

If your JS environment does not support TCO you still have some options available

You can unroll the recursion call and just use a regular loop.


x
 
function addMeUnrolled(n) {
  let acc = 0;
  while (n > 0) {
    acc += n;
    n -= 1;
  }
  return acc;
}
addMeUnrolled(1000000);
x
 
500000500000

You can catch the stack error.

But this is really ugly to have your code depend on errors thrown.


x
 
function addMeTryCatch(n) {
  var acc = 0;
  function __add() {
    if (n < 1) {
      return acc;
    }
    acc = acc + n;
    n = n - 1;
    return __add();
  }
  while( n > 1) {
    try {
      __add();
    } catch (e) {
      console.log('An error was caught');
    }
  }
  return acc;
}
addMeTryCatch(1000000);
x
 
500000500000

You can use trampolining

With trampolining each partial result represents a function call. This function call can either returns another partial result or return the final result.


x
 
function trampoline(res) {
  while (typeof res == 'function') {
    res = res();
  }
  return res;
}
var addMeTrampoline = (function () {
  function addMe(n, acc) {
    if (n < 1) {
      return acc;
    }
    return function partialResult() {
      return addMe(n-1, acc + n);
    }
  }
  return function(x) {
    return trampoline(addMe(x, 0));
  }
})();
addMeTrampoline(1000000);
x
 
500000500000