Tail Call Optimization (TCO)

As we briefly mentioned earlier, ES6 includes a specific requirement that ventures into the world of performance. It’s related to a specific form of optimization that can occur with function calls: tail call optimization.

Briefly, a “tail call” is a function call that appears at the “tail” of another function, such that after the call finishes, there’s nothing left to do (except perhaps return its result value).

For example, here’s a non-recursive setup with tail calls:

function foo(x) {
    return x;
}
function bar(y) {
    return foo( y + 1 );    // tail call
}
function baz() {
    return 1 + bar( 40 );    // not tail call
}
baz();                        // 42

foo(y+1) is a tail call in bar(..) because after foo(..) finishes, bar(..) is also finished except in this case returning the result of the foo(..) call. However, bar(40) is not a tail call because after it completes, its result value must be added to 1 before baz() can return it.

Without getting into too much nitty-gritty detail, calling a new function requires an extra amount of reserved memory to manage the call stack, called a “stack frame.” So the preceding snippet would generally require a stack frame for each of baz(), bar(..), and foo(..) all at the same time.

However, if a TCO-capable engine can realize that the foo(y+1) call is in tail position meaning bar(..) is basically complete, then when calling foo(..), it doesn’t need to create a new stack frame, but can instead reuse the existing stack frame from bar(..). That’s not only faster, but it also uses less memory.

That sort of optimization isn’t a big deal in a simple snippet, but it becomes a much bigger deal when dealing with recursion, especially if the recursion could have resulted in hundreds or thousands of stack frames. With TCO the engine can perform all those calls with a single stack frame!

Recursion is a hairy topic in JS because without TCO, engines have had to implement arbitrary (and different!) limits to how deep they will let the recursion stack get before they stop it, to prevent running out of memory. With TCO, recursive functions with tail position calls can essentially run unbounded, because there’s never any extra usage of memory!

Consider that recursive factorial(..) from before, but rewritten to make it TCO friendly:

function factorial(n) {
    function fact(n,res) {
        if (n < 2) return res;
        return fact( n - 1, n * res );
    }
    return fact( n, 1 );
}
factorial( 5 );        // 120

This version of factorial(..) is still recursive, but it’s also optimizable with TCO, because both inner fact(..) calls are in tail position.

Note: It’s important to note that TCO only applies if there’s actually a tail call. If you write recursive functions without tail calls, the performance will still fall back to normal stack frame allocation, and the engines’ limits on such recursive call stacks will still apply. Many recursive functions can be rewritten as we just showed with factorial(..), but it takes careful attention to detail.

One reason that ES6 requires engines to implement TCO rather than leaving it up to their discretion is because the lack of TCO actually tends to reduce the chances that certain algorithms will be implemented in JS using recursion, for fear of the call stack limits.

If the lack of TCO in the engine would just gracefully degrade to slower performance in all cases, it wouldn’t probably have been something that ES6 needed to require. But because the lack of TCO can actually make certain programs impractical, it’s more an important feature of the language than just a hidden implementation detail.

ES6 guarantees that from now on, JS developers will be able to rely on this optimization across all ES6+ compliant browsers. That’s a win for JS performance!