How to Implement a Trampoline for Tail Recursion in Python

This code implements a trampoline decorator that converts tail-recursive functions into iterative loops, allowing deep recursion without hitting Python's recursion limit.

Medium Python 3.9+ Aug 9, 2026 Functions & basics 12 views 0 copies

trampoline tail-recursion decorator recursion functional

Python code

20 lines

Python 3.9+

def trampoline(fn):
    """Convert a tail-recursive function into an iterative loop."""
    def wrapper(*args, **kwargs):
        result = fn(*args, **kwargs)
        while callable(result):
            result = result()
        return result
    return wrapper

@trampoline
def factorial(n, acc=1):
    """Tail-recursive factorial using a thunk for the recursive call."""
    if n <= 1:
        return acc
    return lambda: factorial(n - 1, acc * n)

if __name__ == "__main__":
    # Works for large n without hitting Python's recursion limit
    print(f"Factorial of 5: {factorial(5)}")
    print(f"Factorial of 1000: {factorial(1000)}")

Output

stdout

Factorial of 5: 120
Factorial of 1000: 4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668725448085669873054310591020741955780764281977859793965525635961545209183229188820587689769159389021012597969198466120516986469280748580094389953330237874380760529024942973881292936196874733846056348992303695173585810954081914790917138965661423549543032292270433556723340788445223141552291151548856947233492458399222029317557041150686242824496360326742674759823405276870297987679989756481740888634907745813862493965188513232961284428394782850589654164803442681253833805964734776529861670865306870174975129529449943364934546562495517809301659031165496011549296175253460141246775453046370544798066857867

How it works

The trampoline decorator wraps the function so that each recursive call returns a lambda (thunk) instead of recursing directly. The wrapper then repeatedly invokes the thunk in a while loop, turning recursion into iteration and avoiding stack overflow. This works because the recursion is in tail position — the recursive call is the last operation — allowing the thunk to delay evaluation. The factorial function uses an accumulator parameter to maintain state across iterations, and the loop terminates when the result is no longer callable.

Common mistakes

Forgetting to return a thunk in the recursive case, causing direct recursion that still hits the recursion limit.
Not handling the base case correctly — the function must return a non-callable value to stop the trampoline loop.
Assuming the trampoline works for non-tail-recursive functions; it only converts tail calls.
Using mutable default arguments or shared state across thunks, leading to unexpected results.

Variations

Use a while loop inside the function itself instead of a decorator, if you prefer explicit iteration.
Replace the lambda thunk with a `functools.partial` for better performance in tight loops.

Real-world use cases

Implementing deep tree traversals in functional style without recursion limits in data processing pipelines.
Parsing deeply nested expressions or JSON-like structures where recursion depth is unbounded.
Simulating tail-call optimization in Python for algorithms that naturally recurse, like state machines in game logic.

How to Implement a Trampoline for Tail Recursion in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Functions & basics

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Functions & basics

Keep learning

Tutorials

Quizzes