THE TRAMPOLINE bounce tail calls back to a top loop — constant stack, no matter how deep
A trampoline gives a language constant-stack tail recursion even when its runtime does not optimize tail calls. Instead of a tail call calling (and growing the stack), the function returns a small thunk describing the next call; a top-level loop — the trampoline — keeps invoking whatever it is handed until a real value comes back. The stack never grows past one frame, because every call returns before the next begins. It is the standard workaround in JavaScript, Java, Python — any host without guaranteed tail-call optimization — and the cleanest illustration of what TCO buys you.
THE TECHNIQUE return the next call as a thunk; a top loop bounces until a value
A tail-recursive sum 1..n run trampolined. The demo bounces once per step, keeping the stack flat, and totals to 5050 at n=100: live demo
HISTORY & CREDIT Ganz, Friedman & Wand, 1999
“Deep recursion must overflow the stack.” — a trampoline turns each tail call into a return plus a bounce, so the stack stays one frame deep however many times you recur. Depth becomes iterations, not frames. cited
1999 · Ganz, Friedman & Wand — “Trampolined Style”: return-a-thunk, bounce in a loop, for constant-stack tail calls. lineage · the workaround for hosts without the tail-call optimization Steele argued for (1977). now · standard in JS/Java/Python; libraries like clojure.core/trampoline.
Return the next call instead of making it, and a million-deep recursion runs in one stack frame. The trampoline is TCO you can build by hand when the machine won't give it to you. Ganz-Friedman-Wand 1999
RECOMMEND FOR I-13 trampolined sum + i13's real frame ceiling, computed
On the canonical compiler, the tail-recursive sum 1..100 = 5050 runs at call depth 101 — i13 nests a real frame per step, comfortably under its 4096-frame ceiling here:
$ i13 run m_trampoline.i13 # sum 1..100, tail recursion
RUN OK . 1517 step(s) . peak stack 5 . call depth 101
result = 5050
bounces = 100
Recommend: this is the one dart in the batch that names a real i13 frontier. i13's tail recursion nests real frames — call depth 101 for n=100 — and its recursion is bounded at 4096 frames (E0503), so a tail-recursive loop past ~4096 iterations halts rather than looping forever. A trampoline (or true tail-call optimization) is exactly the mechanism that would let i13 run unbounded tail loops in constant stack. It is a genuine open recommend — TCO is on i13's frontier list — and the honest one: not “i13 already does this,” but “here is the bounded behavior, and here is the machine trick that lifts the bound.”