trampoline<T> function

T trampoline<T>(Bounce<T> bounce)

Executes a bouncing computation until completion without recursion.

The trampoline pattern prevents stack overflow by replacing recursive function calls with iterative execution. Instead of making recursive calls directly, return a More bounce with a thunk that will be executed next.

This is particularly useful for:

• Tree traversals that could overflow the stack
• Deep recursive algorithms (parsing, DFS, etc.)
• Tail-recursive patterns that can't be optimized by the compiler

How it works:

1. Start with an initial Bounce (usually More)
2. Each More returns a function that produces the next Bounce
3. The trampoline executes these functions in a loop (not recursion)
4. When Done is reached, the final value is returned

Example:

// Calculate factorial without recursion overflow
Bounce<int> factorialBounce(int n, int acc) {
  if (n <= 1) {
    return Done(acc);
  }
  return More(() => factorialBounce(n - 1, n * acc));
}

final result = trampoline(More(() => factorialBounce(5, 1)));
// result = 120

Implementation

T trampoline<T>(Bounce<T> bounce) {
  var current = bounce;

  while (current is More<T>) {
    current = current.next();
  }

  assert(current is Done<T>);

  return (current as Done<T>).value;
}