Write trampoline(fn) so a recursive function can run a million steps deep without overflowing the stack.
Before you start
What's a trampoline?
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 function with no parameters (a thunk) that performs the next step.
trampoline(fn) returns a new function. Calling it calls fn with the same arguments and this. Then it keeps calling the thunks it gets back, in a loop, until it gets a value that isn't a function, and returns that value.
function trampoline(fn) {
// your code
}
// const sumTo = trampoline(function step(n, total = 0) {
// return n === 0 ? total : () => step(n - 1, total + n);
// });
// sumTo(3); // 6. The calls are step(3, 0), step(2, 3), step(1, 5), and step(0, 6),
// // each after the first made by the thunk the one before returned. step(0, 6) returns 6.
// sumTo(1_000_000); // 500000500000, with no stack overflow
Solve it in the editor, with tests
The answer
Write it yourself first. Then compare it with a reference solution and the checks it passes.
Checking your sign-in…