Tail Call Optimization in JavaScript using Trampolines

Continuing on the previous article in this series. With some preparation and slight modifications to our existing code we can perform tail call optimization (TCO) to make an unlimited number of recursive function calls in JavaScript!

Below is the full solution based on this example from Stack Overflow. We'll break everything down in a moment:

class Tco {        
  constructor(func) {
    this.func = func;
  }
  execute() {
    let value = this;
    while (value instanceof Tco)
      value = value.func(); 
    return value;  
  }
}

const tco = (f) => new Tco(f);

function adder(n) {
  const loop = (i) => tco(() => {
    if (i == n) {
      return n;
    }     
    return loop(i + 1);
  });

  return loop(0).execute();
};

console.log(adder(10)); 
console.log(adder(1000));
console.log(adder(100000));
console.log(adder(10000000));  

pi@raspberrypi:~/Documents $ node adder.js 
10
1000
100000
10000000

Trampolines

The Tco class defines an object with an execute function that does the heavy lifting:

    let value = this;
    while (value instanceof Tco)
      value = value.func(); 
    return value; 

This is an example of a trampoline. Sadly, there is no trampoline emoji or I would throw one in here. Anyhow, this while loop calls a function value.func() that returns either:

• A Tco instance to indicate execution is still active. The trampoline will call into that instance again to make another recursive call, or
• A different type of object indicating recursion is complete. This value is returned as the final result

Helper Function

A tco function is defined as a helper to make the syntax cleaner:

const tco = (f) => new Tco(f);

Modifying our Existing JavaScript Code

The adder function's inner loop is modified to return an instance of Tco via our helper function.

When we say return loop we are returning that instance to the caller rather than calling into loop directly!

Note the return n returns our final integer value, terminating the loop:

  const loop = (i) => tco(() => {
    if (i == n) {
      return n;
    } 
    return loop(i + 1);
  });

Finally, we begin our loop by instantiating a loop object and calling into its execute function to start the Tco object's while loop:

  return loop(0).execute();

Wrapping Up

While this pattern might not be a good idea for writing day to day code it can be a useful tool. Interpreters written in an imperative language such as JavaScript often use a trampoline to implement tail call optimization for the language that they are hosting. For example this would be an excellent start to the core of a Lisp interpreter in JavaScript.

And that's it! Thanks for reading 👍