Trampoline (computing)

In computer science, a trampoline is a programming technique used primarily for control flow, especially in languages that lack proper tail call optimization (TCO) or have limited stack space. It allows for mutual recursion between functions (where functions call each other indirectly) to be implemented without growing the call stack indefinitely, thus avoiding stack overflow errors.

The core concept of a trampoline is to transform recursive calls into iterative calls. Instead of a function calling itself or another function directly, it returns a special object or data structure representing the next function to be called. This object essentially encapsulates the function and its arguments. A loop, called the "trampoline," then repeatedly executes these returned function objects until a final result is reached.

Specifically, a function designed to work with a trampoline returns a "thunk" – a function closure that encapsulates a computation to be performed later. The trampoline then evaluates this thunk. If the thunk returns another thunk, the trampoline continues the process. If the thunk returns a regular value (i.e., not another thunk), the trampoline terminates and returns that value as the final result.

This approach effectively moves the recursion from the call stack into the heap, allowing for unbounded recursion within the limits of available memory. The trampoline loop provides the iterative control flow that drives the computation. Trampolines are most useful in functional programming paradigms where recursion is frequently used for iterative processes.