When a function calls itself, each call waits for the one it made to return. While it waits, its frame, the record of its arguments, local variables, and where to carry on, stays on the call stack. The call stack has a limited size, so recursion that goes too deep runs out of room: Chrome, Node, and Safari throw RangeError: Maximum call stack size exceeded, and Firefox throws InternalError: too much recursion. A trampoline is a way to run deep recursion without growing the stack.
function sumTo(n) {
if (n === 0) return 0;
return n + sumTo(n - 1); // waits here for sumTo(n - 1)
}
sumTo(3); // 6: sumTo(3) waits for sumTo(2), which waits for sumTo(1), ...
sumTo(1_000_000); // RangeError: a million frames don't fit on the stack
The trick uses thunks. A thunk is a function with no parameters that wraps a call to make later: () => sumTo(n - 1) is a thunk, and nothing runs until someone calls it. The recursive function is rewritten so that, instead of calling itself, it returns a thunk for its next step, or the final value when it's done. Work that used to happen after the call, like the n +, moves into an argument that carries the running total:
function sumTo(n, total = 0) {
if (n === 0) return total;
return () => sumTo(n - 1, total + n); // the next step, not run yet
}
sumTo(3); // a function: a thunk for sumTo(2, 3)
sumTo(3)()()(); // 6: calling each thunk by hand runs one step at a time
| Question | Plain recursion | Returning thunks |
|---|---|---|
| What does each step do? | Calls the next step and waits for its result | Hands back a thunk that would make the next call, and is finished |
| Who makes the next call? | The step itself | Whoever called the step, after it has returned |
How many frames does sumTo(1_000_000) need? | A million at once, so it overflows | A few at a time, however large n is |
A trampoline is the driver that runs those steps for you, one after another, until a step returns a final value instead of a thunk. Every step returns to the trampoline before the next one starts, so control keeps bouncing back to it, which is where the name comes from.
You need one when how deep the recursion goes depends on the data, such as walking a linked list a million nodes long, or recursing once for each item of a long array.
fn is a recursive function written so that it never calls itself directly. Each call returns either the final value, or a thunk: a function with no parameters that performs the next step when it's called.
Write trampoline(fn). It returns a new function. Calling that function calls fn with the same this and arguments. Then, as long as the result is a function, it calls that function with no arguments and takes its result instead. The first result that isn't a function is returned, whatever its type.
The stack must not grow with the number of steps: a function that takes 100,000 steps, more nested calls than any browser's stack can hold, must run without a stack overflow.
const sumTo = trampoline(function step(n, total = 0) {
return n === 0 ? total : () => step(n - 1, total + n);
});
sumTo(3); // 6: step(3, 0), then step(2, 3), step(1, 5), and step(0, 6)
sumTo(100_000); // 5000050000, with no stack overflow
const fn = spy((x) => x * 2);
expect(trampoline(fn)(21)).toBe(42);
expect(fn).toHaveBeenCalledTimes(1);
const thunks = [];
const sumTo = trampoline(function step(n, total = 0) {
if (n === 0) return total;
const thunk = spy(() => step(n - 1, total + n));
thunks.push(thunk);
return thunk;
});
expect(sumTo(3)).toBe(6);
expect(thunks).toHaveLength(3);
expect(thunks.map((thunk) => thunk.callCount)).toEqual([1, 1, 1]);
const sumTo = trampoline(function step(n, total = 0) {
return n === 0 ? total : () => step(n - 1, total + n);
});
expect(sumTo(100_000)).toBe(5000050000);
const isEven = (n) => (n === 0 ? true : () => isOdd(n - 1));
const isOdd = (n) => (n === 0 ? false : () => isEven(n - 1));
expect(trampoline(isEven)(100001)).toBe(false);
expect(trampoline(isOdd)(100001)).toBe(true);
const last = { id: 3 };
const walk = trampoline(function step(node) {
return node.next ? () => step(node.next) : node;
});
expect(walk({ id: 1, next: { id: 2, next: last } })).toBe(last);
expect(trampoline(() => () => "done")()).toBe("done");
expect(trampoline(() => () => 0)()).toBe(0);
expect(trampoline(() => () => null)()).toBeNull();
expect(trampoline(() => () => undefined)()).toBeUndefined();
const fn = spy(function (a, b) {
return this.base + a + b;
});
const obj = { base: 100, run: trampoline(fn) };
expect(obj.run(1, 2)).toBe(103);
expect(fn.calls[0].this).toBe(obj);
expect(fn.calls[0].args).toEqual([1, 2]);
Run tests runs every test on your code, here in your browser. The problem is solved when they all pass.
Ctrl + Enter runs the tests (⌘ + Enter on a Mac).
I'm here to help with Trampoline. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.