Trampolines - fun way to make recursion not stack overflow

(We'll use JavaScript for today, running in the Firefox developer console.)

No doubt when you learned recursion, you learned that each recursive function call uses stack space to do its work.  There's only so much stack space.  So unless your programming language has a special feature (called tail call elimination), a recursive function can eventually exhaust all stack space, leading to the famous stack overflow error (not the web site).

For example, let's write a loop to sum up numbers from 0 up to some N like this:

let sum = 0;
for (let i = 0; i < 10000; ++i) sum += i;
console.log(sum); // prints: 49995000

Now a recursive version might look like this:

const loop = function(i, sum){
  if (i < 10000){
    sum += i;
    return loop(i + 1, sum);
  } else {
    return sum;
  }
};
console.log(loop(0, 0)); // prints: 49995000

As you can see, a loop is just a recursive function call.

The above is a nice, simple demo of converting a loop to recursion.  But if instead of summing up to 10,000, we sum up to 100,000, then the loop prints 4999950000.  But the recursive function prints:

Uncaught InternalError: too much recursion

With a link to: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Errors/Too_much_recursion

Trampolines

No surprise, like the title says, trampolines can fix this!

The key is to not allow the loop function to run loop(i + 1, sum), because that'd consume stack space!  Instead, the loop function will return a function called a thunk.  That thunk function, when run, will run and return loop(i + 1, sum).  This also means a thunk can return a thunk!

The function that runs loop, and any thunk functions, is called a trampoline.  That's because the thunk function the trampoline runs may return a thunk, and if so, that thunk will get run too.  The thunks keep bouncing off of the trampoline function.  Until one day a thunk returns a value instead of a thunk!  Then the trampoline's job is done, and that value is returned.

Because the thunk itself only ever uses a single "frame" of space on the stack, rather than recursively using more and more stack space with recursive function calls, and so the stack overflow error is avoided.

Here's how the code will look:

const loop = function(i, sum){
  if (i < 100000){
    sum += i;
    let thunk = ()=>{return loop(i + 1, sum)};
    return thunk; // rather than returning loop(i + 1, sum)
  } else {
    return sum;
  }
};
 

const trampoline = function(){
  let tv = loop(0, 0);
  while (typeof tv === 'function'){
    tv = tv(); // returns either a thunk function or a value
  }
  return tv;
};
 

console.log(trampoline()); // prints: 4999950000

Trampolines running thunk-returning thunk functions is a generic technique that's applicable in other languages and situations too!

Tail Call Elimination: no need for trampolines

If your programming language has full support for an optimization called Tail Call Elimination, the above trampoline technique is completely unnecessary.

It turns out JavaScript at one point had this optimization planned.  It was to be an "invisible" opportunistic tail call optimization (TCO).  Meaning that if you correctly wrote a proper recursive function call in tail position, then TCO would kick in, and it wouldn't consume stack space (thus no stack overflow).

TCO is currently only available on Apple's Safari browser and on iOS [1].

Google's V8 team apparently came to the conclusion that TCO makes the wrong tradeoff.  Because it's an opportunistic optimization, it's very easy for a programmer to write code they think would get TCO, but actually won't, and it can be very difficult to discover the error during testing.  They advocated for an explicit syntactic way to designate a recursive function call as requiring tail call elimination.  But... well, it all fell by the wayside and was never picked back up [2].

Interestingly, the Clojure programming language's creator, Rich Hickey, basically made the same argument.  In Clojure, recursive function calls requiring TCO must be written explicitly with a recur syntax.  In that case, no trampoline is needed, and the recursive function call won't overflow the stack.

 

[1] https://kangax.github.io/compat-table/es6/

[2] https://stackoverflow.com/a/42788286