Proper Tail Calls (PTC) in JavaScript

I heard the term "Proper Tail Call" several times already and it always felt like magic to me. And even when I read a few articles already I never really got it... until today. 🎉

I watched the talk "Functional Programming Basics in ES6" by Jeremy Fairbank and later read the article "All About Recursion, PTC, TCO and STC in JavaScript" by Lucas F. Costa and I finally got it.

Let's assume you have this script:

function factorial(n) {
    console.trace();
    if (n === 0) {
        return 1;
    }
    
    // no proper tail call
    return n * factorial(n - 1);
}

factorial(2);

It will output the following when being executed with in Node.js:

Trace
    at factorial (/private/tmp/ptc.js:4:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:4:13)
    at factorial (/private/tmp/ptc.js:9:16)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:4:13)
    at factorial (/private/tmp/ptc.js:9:16)
    at factorial (/private/tmp/ptc.js:9:16)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...

You see that the call stack gets bigger and bigger due to the recursive nature of factorial. This can lead to the famous RangeError: Maximum call stack size exceeded error when you execute it with a really high number (I tried it with 100000 and it failed).

If you now optimize the function in the script to do proper tail calls you can get around this problem.

'use strict';

function factorial(n, total = 1) {
    console.trace();
    if (n === 0) {
        return total;
    }

    // proper tail call
    return factorial(n - 1, n * total);
}

factorial(2);

Now the output looks as follows.

Trace
    at factorial (/private/tmp/ptc.js:13:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:13:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...
Trace
    at factorial (/private/tmp/ptc.js:13:13)
    at Object.<anonymous> (/private/tmp/ptc.js:21:1)
    ...

You see – there is no increase in call stack size. 🎉 This means that this way you don't run into the Maximum call stack size exceeded error. Cool stuff!

There are some constraints though. Lucas describes them in his article as follow:

In order to have access to proper tail calls on Node, we must enable strict mode by adding 'use strict' to the top of our .js file and then run it with the --harmony_tailcalls flag.

I could now go into the details of this topic and describe what makes a proper tail call but Lucas and Jeremy did this already way better than I could. So in case this is also new to you I highly recommend checking out the talk and the article.

Side note: at the time of writing proper tail calls are only supported by Safari and Webkit browsers.