CONCEPT 15 · EFFECTS & IO

Trampolining & Stack Safety

"Turn deep recursion into a loop — zero stack overflow risk."

recursionstack safetyperformance

Plain English

Trampolining converts deep recursion into a loop that never overflows the stack. Instead of calling the next step (which adds a stack frame), you return a description of the next step — a thunk (a zero-argument function). A simple loop then calls each thunk one at a time. Stack depth stays at O(1) regardless of how many steps there are.

Analogy

Instead of stacking meetings inside meetings (each one waiting for the inner one to finish — which fills your schedule forever), you write each next action on a sticky note and put it in a queue. One worker processes the queue one note at a time. The queue lives on a desk (heap) which is practically unlimited. The stack of nested meetings is the problem; the queue is the solution.

You already know this

JavaScript's event loop: tasks are queued, not nested. Async callbacks don't stack — they queue.Node.js setImmediate / process.nextTick: defers the next step instead of calling it directlyIterative tree traversal with an explicit stack (array): same idea — heap replaces call stackContinuation-passing style (CPS): passing "what to do next" as a function argumentThe call stack IS the problem. Any while loop with a queue is a trampoline.

Code Example

JavaScript

// NAIVE RECURSION — crashes on large inputs
function sumTo(n: number): number {
  if (n === 0) return 0;
  return n + sumTo(n - 1); // each call adds a stack frame
}
sumTo(100000); // → RangeError: Maximum call stack size exceeded

// TRAMPOLINED — O(1) stack, works on any n
type Thunk<A> = () => A | Thunk<A>;

function sumToTramp(n: number, acc = 0): number | Thunk<number> {
  if (n === 0) return acc;
  return () => sumToTramp(n - 1, acc + n); // return a THUNK, not a call
}

function trampoline<A>(fn: (...args: unknown[]) => A | Thunk<A>) {
  return function(...args: unknown[]): A {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result(); // call the thunk — stack stays at depth 1
    }
    return result as A;
  };
}

const safeSumTo = trampoline(sumToTramp);
safeSumTo(100000); // → 5000050000 ✓ no overflow

// Why it works:
// Recursive:    call → call → call → call (N frames deep) → BOOM
// Trampolined:  call → thunk → loop → thunk → loop (always 1 frame)

// Real-world: trampolining is built into many FP libraries
// Cats Effect (Scala), ZIO, and Haskell's RTS all use this internally

Apply when

▸Deep recursion that crashes with "Maximum call stack size exceeded" or stack overflow

▸Processing deeply nested structures: deep JSON, ASTs, recursive data types

▸Mutual recursion between many functions (A calls B calls A calls B...)

▸Implementing interpreters, compilers, or state machines that run for many steps

▸Any recursive algorithm on data with unknown/unbounded depth

Check Your Understanding

Your recursive function crashes with "Maximum call stack size exceeded" on lists of 50,000+ items. What is the most direct fix?

◀ PREVDescription vs ExecutionNEXT ▶Stream Processing

Trampolining & Stack Safety

JARGON DECODER