Trampoline a deep recursion

hardFunctions & Closures+350 XPPractice

JavaScript has no guaranteed tail-call optimisation, so a recursion a hundred thousand deep throws a stack overflow. A trampoline sidesteps this: the recursive function, instead of calling itself, returns a zero-argument function — a thunk — describing the next step, and a driver loop keeps calling thunks until a real value comes back. The stack never grows past one frame.

Implement trampoline(fn). It returns a wrapper that calls fn with all of the arguments it was given, then, as long as the result is a function, calls that result with no arguments, repeating until the result is not a function, and returns that final value. If fn returns a non-function straight away, the wrapper returns it as-is. Because each bounce is a fresh call from the loop rather than a nested call, a recursion of any depth is safe, and thunks may point at a different function each bounce, which makes mutual recursion work too.

Arguments

fnFunction: A recursive function that returns either a plain value (done) or a thunk (() => nextStep).

Returns

Function — A wrapper that drives thunks in a loop, surviving arbitrarily deep recursion.

Examples

const sumTo = trampoline(function go(n, total) {
  if (n === 0) return total;
  return () => go(n - 1, total + n);
});

sumTo(100000, 0); // 5000050000 — a plain recursive version would overflow

Each bounce is a fresh call from the loop, so the stack never grows past one frame.

function isEven(n) { return n === 0 ? true : () => isOdd(n - 1); }
function isOdd(n)  { return n === 0 ? false : () => isEven(n - 1); }

trampoline(isEven)(50000); // true — mutual recursion works the same way

What it has to do

Call fn with every argument the wrapper received.
Keep invoking the returned thunk, with no arguments, while the result is a function.
Return the first non-function result, including when fn returns one immediately.
Survive a recursion deep enough to overflow the call stack.
Work when the thunks alternate between two mutually recursive functions.

Notes

The whole wrapper is one while (typeof result === 'function') result = result() loop around the first call. Thunks take no arguments because the recursive function has already closed over everything the next step needs.
This is how you simulate tail-call optimisation in JS, which does not guarantee TCO. Writing to this shape also makes the step-by-step state explicit, which is handy for debugging.

Stuck? The javascript course covers everything this challenge needs.

Try it yourself· Edit the code, then press Run

Loading playground...

5 tests · +350 XP

Discussion

No comments yet. Be the first to say something.

All challenges92 / 150