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 👍
Top comments (0)