Proper Tail Calls (PTC) in JavaScript

Whenever I hear the term "Proper Tail Call", it feels like magic because it's hard to grok. But today I finally made some progress in understanding proper tail calls and tail call optimization.

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.

Let's look at an example and assume you have this script:

function factorial(n) {
  console.trace();

  if (n === 0) {
    return 1;
  }
    
  // ❌ no proper tail call
  // The return value is based on the multiplication
  // of `n` and `factorial()`.
  return n * factorial(n - 1);
}

factorial(2);

It will output the following trace output when being executed 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 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 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 the increasing call stack problem.

'use strict';

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

    // ✅ proper tail call
    // The return value is based on a single function call.
    // 
    // `total` and `n` can be passed to the function and go
    // onto it's own callstack.
    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 and you don't run into the Maximum call stack size exceeded error anymore. Cool stuff!

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

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.