Trampolines: Recursive Control Flow Through a Loop

Can even(5) ask odd(4) to continue without keeping its own activation waiting? Step through Trampoline and watch each worker return to the loop, then compare Direct at the same starting value.

def even(n):    if n == 0: return Done(True)    return Call(lambda: odd(n - 1))def odd(n):    if n == 0: return Done(False)    return Call(lambda: even(n - 1))def run(step):    while isinstance(step, Call):        step = step.thunk()    return step.valueresult = run(Call(lambda: even(n)))

Return the next step

A trampoline is a loop that repeatedly executes a deferred step. A worker returns a description of the next call instead of making that call immediately. The worker finishes, control returns to the loop, and the loop starts the next step. This removes the growing chain of worker calls when every recursive handoff follows that protocol. Bjarnason's Stackless Scala paper, section 3 develops this transformation using mutually recursive even and odd functions.

A thunk is a function taking no arguments that represents work to perform later. In Python, lambda: odd(n - 1) creates such a function. Creating it does not call odd. Calling the thunk later performs the deferred call, using the n captured from this worker's activation.

The distinction is one pair of parentheses:

# examples/trampoline_handoff.py
return odd(n - 1)                # Call now; wait for its result.
return Call(lambda: odd(n - 1))  # Return deferred work to the loop.

These are alternative return statements inside a worker. Call stores the thunk; it does not invoke it. Writing Call(odd(n - 1)) would evaluate the recursive call immediately and defeat the transformation.

A small Call/Done protocol

The loop needs two unambiguous messages:

• Call(thunk) means there is another deferred step to execute.
• Done(value) means execution has finished and value is the result.

Scala's standard-library TailCalls exposes the same distinction through tailcall and done. Here is a complete Python version. The parity functions assume a nonnegative integer; decrementing a negative input would never reach their base case.

# examples/trampoline_parity.py
from dataclasses import dataclass
from typing import Callable


@dataclass(frozen=True)
class Call:
    thunk: Callable[[], object]


@dataclass(frozen=True)
class Done:
    value: object


def run(step):
    while isinstance(step, Call):
        step = step.thunk()
    if not isinstance(step, Done):
        raise TypeError("Expected Call or Done")
    return step.value


def even(n):
    if n == 0:
        return Done(True)
    return Call(lambda: odd(n - 1))


def odd(n):
    if n == 0:
        return Done(False)
    return Call(lambda: even(n - 1))


result = run(Call(lambda: even(5)))
assert result is False

The initial Call also defers the first worker. On each loop iteration, step.thunk() calls one parity worker and receives its next token. That invocation finishes before the next iteration begins. At the base case the worker returns Done, the loop condition becomes false, and run returns the wrapped Boolean.

Why use tags instead of while callable(step)? A function can be legitimate result data. With an explicit Done, the loop returns that function unchanged:

# examples/trampoline_callable_result.py
callback = lambda: "saved callback"
assert run(Done(callback)) is callback

Here the loop never invokes callback. The tag determines whether there is work to run; the type of the result does not.

Follow the base case all the way back

For even(5), the sequence is even(5) → odd(4) → even(3) → odd(2) → even(1) → odd(0). The base case is odd(0), so the answer is False. With even(4), the sequence ends at even(0) and returns True. Starting at zero immediately selects even's True base case.

In direct recursion, each caller waits to forward the child's answer. There is no pending addition or Boolean negation, but those ordinary activations remain until the calls return unless the runtime eliminates them. The figure deliberately assumes no such elimination.

In the trampoline, even(5) returns Call and finishes before odd(4) starts. The loop then repeats that pattern. Done(False) is first returned to the loop, which unwraps it and returns False to the original caller. The explorer gives that final return its own step so the base case and the completed computation remain distinct.

Bounded call depth has a cost

For a countdown starting at n, the direct model reaches n + 1 live parity activations. The trampoline has at most one live parity activation at a time. Its loop and thunk calls still use activations; their overhead is bounded in this example and omitted from the figure's parity-only count. These are symbolic control-flow counts, not observations of CPython's native stack or a profiler.

The trampoline still performs n + 1 parity-worker invocations. Each non-base worker allocates a new Call and a closure, so the total number of allocations grows with the countdown. Consuming a token and dropping references can keep the live control state small for this example. Retaining a history of tokens, capturing large objects, or storing pending continuations can increase heap use. The explorer itself stores its full teaching trace so that Previous works.

This is the stack-for-heap trade described in the Stackless Scala paper. Extra allocation and loop dispatch can cost time, and trampolining does not guarantee a speedup. Its purpose here is to change how control moves, with predictable worker-call depth.

Tail calls, continuations and state machines

Tail-call optimization lets a compiler or runtime transfer to the next function without retaining the current activation when its result can be forwarded directly. A trampoline changes the source program: workers return tokens, and an explicit loop performs later calls. It can therefore handle this mutual recursion without relying on native tail-call elimination.

CPython does not provide tail-call optimization for Python function calls. Its optional tail-call interpreter changes dispatch between internal C opcode handlers. Using a Python trampoline does not enable a new Python-function optimization. Python's release notes make that distinction explicitly.

Continuation-passing style makes pending computation explicit. A trampoline can execute deferred continuation steps too, but writing CPS alone does not make ordinary calls stack-safe in a runtime without tail-call elimination. Every potentially growing call path must return to the driver rather than recursively invoking the next continuation. The parity example needs no stored arithmetic continuation because each answer is simply forwarded.

The protocol also resembles a state machine: the current token describes where execution resumes. Replacing the closures with a state tag such as EVEN or ODD, plus the remaining count, produces a data-driven loop. Interpreter dispatch explores another place where a driver chooses which piece of work runs next. Its bytecode handlers and this page's parity workers are different levels of execution.

When is a trampoline useful?

Trampolining can preserve separate, mutually recursive functions when a direct rewrite into one loop would obscure their structure. It is also useful when deferred computation is already represented by a library's control protocol, as in Scala's TailCalls.

For this parity calculation, a modulo operation is clearer in production. For a simple accumulator recursion, an ordinary loop is often easier to read and avoids allocating a closure for each step. Use a trampoline when the explicit handoff helps organize the problem, then measure the actual workload if speed or memory is the reason for the change.

Related concepts