Tail Call Optimization

Perhaps the most interesting change to functions in ECMAScript 6 is an engine optimization, which changes the tail call system. A tail call is when a function is called as the last statement in another function, like this:

function doSomething() {
    return doSomethingElse();   // tail call
}

Tail calls as implemented in ECMAScript 5 engines are handled just like any other function call: a new stack frame is created and pushed onto the call stack to represent the function call. That means every previous stack frame is kept in memory, which is problematic when the call stack gets too large.

What’s Different?

ECMAScript 6 seeks to reduce the size of the call stack for certain tail calls in strict mode (nonstrict mode tail calls are left untouched). With this optimization, instead of creating a new stack frame for a tail call, the current stack frame is cleared and reused so long as the following conditions are met:

1. The tail call does not require access to variables in the current stack frame (meaning the function is not a closure)
2. The function making the tail call has no further work to do after the tail call returns
3. The result of the tail call is returned as the function value

As an example, this code can easily be optimized because it fits all three criteria:

"use strict";
function doSomething() {
    // optimized
    return doSomethingElse();
}

This function makes a tail call to doSomethingElse(), returns the result immediately, and doesn’t access any variables in the local scope. One small change, not returning the result, results in an unoptimized function:

"use strict";
function doSomething() {
    // not optimized - no return
    doSomethingElse();
}

Similarly, if you have a function that performs an operation after returning from the tail call, then the function can’t be optimized:

"use strict";
function doSomething() {
    // not optimized - must add after returning
    return 1 + doSomethingElse();
}

This example adds the result of doSomethingElse() with 1 before returning the value, and that’s enough to turn off optimization.

Another common way to inadvertently turn off optimization is to store the result of a function call in a variable and then return the result, such as:

"use strict";
function doSomething() {
    // not optimized - call isn't in tail position
    var result = doSomethingElse();
    return result;
}

This example cannot be optimized because the value of doSomethingElse() isn’t immediately returned.

Perhaps the hardest situation to avoid is in using closures. Because a closure has access to variables in the containing scope, tail call optimization may be turned off. For example:

"use strict";
function doSomething() {
    var num = 1,
        func = () => num;
    // not optimized - function is a closure
    return func();
}

The closure func() has access to the local variable num in this example. Even though the call to func() immediately returns the result, optimization can’t occur due to referencing the variable num.

How to Harness Tail Call Optimization

In practice, tail call optimization happens behind-the-scenes, so you don’t need to think about it unless you’re trying to optimize a function. The primary use case for tail call optimization is in recursive functions, as that is where the optimization has the greatest effect. Consider this function, which computes factorials:

function factorial(n) {
    if (n <= 1) {
        return 1;
    } else {
        // not optimized - must multiply after returning
        return n * factorial(n - 1);
    }
}

This version of the function cannot be optimized, because multiplication must happen after the recursive call to factorial(). If n is a very large number, the call stack size will grow and could potentially cause a stack overflow.

In order to optimize the function, you need to ensure that the multiplication doesn’t happen after the last function call. To do this, you can use a default parameter to move the multiplication operation outside of the return statement. The resulting function carries along the temporary result into the next iteration, creating a function that behaves the same but can be optimized by an ECMAScript 6 engine. Here’s the new code:

function factorial(n, p = 1) {
    if (n <= 1) {
        return 1 * p;
    } else {
        let result = n * p;
        // optimized
        return factorial(n - 1, result);
    }
}

In this rewritten version of factorial(), a second argument p is added as a parameter with a default value of 1. The p parameter holds the previous multiplication result so that the next result can be computed without another function call. When n is greater than 1, the multiplication is done first and then passed in as the second argument to factorial(). This allows the ECMAScript 6 engine to optimize the recursive call.

Tail call optimization is something you should think about whenever you’re writing a recursive function, as it can provide a significant performance improvement, especially when applied in a computationally-expensive function.