How to Overcome Python's Recursion Limit

With Lambdas and Trampolines

Gwang-Jin Kim

27 Jul 2025 • 5 min read

Photo by Parrish Freeman / Unsplash - Recursion

Most people who hit Python’s recursion limit do the sensible thing: they rewrite their recursive function as a loop, mutter something about tail-call optimization, and get on with their lives.

But some of us — the stubborn, the curious, the lovers of clean functional idioms — ask a different question:

“What if I didn’t rewrite it as a loop? What if I could keep my recursion… and make Python play nice?”

Well, grab your favorite beverage. We’re about to outsmart Python’s call stack with nothing but a few lambdas, some deferred evaluation, and a pattern called the trampoline.

Scene 1: The Naïve Recursive Hero

Let’s start with the classic example: factorial.

def fact(n):
    return 1 if n == 0 else n * fact(n - 1)

It works for small numbers. But call fact(5000) and the interpreter bursts into flames:

RecursionError: maximum recursion depth exceeded

Why? Python doesn’t do tail-call optimization (TCO). Each recursive call stacks on top of the previous one. After ~1000 calls, you run out of room.

If you’re from the Scheme world, this is offensive. If you’re from the Python world, it’s expected.

But you want more.

Scene 2: A Glimmer of Hope — Tail Recursion?

Let’s try refactoring it to a tail-recursive style:

def fact(n, acc=1):
    return acc if n == 0 else fact(n - 1, acc * n)

Nice! The recursive call is in tail position. That means, in some languages, the compiler could throw away the current frame and reuse it for the next.

Python says: “That’s adorable,” and still gives you:

RecursionError: maximum recursion depth exceeded

Because again: Python does not optimize tail calls. On purpose.

Scene 3: How to Lie to the Call Stack — The Trampoline Trick

Here’s the deal: we can fake recursion using lambdas.

Instead of calling the next step, we return a function that would call it — later. Then we run a loop that keeps evaluating those lambdas until we get a final value.

That’s called a trampoline. Because each step bounces to the next, but stays in the same stack frame.

Here’s the whole pattern in one go:

def trampoline(f):
    while callable(f):
        f = f()
    return f

That’s the whole engine. Now let’s plug in a factorial that returns lambdas instead of doing direct recursion:

def fact(n, acc=1):
    return acc if n == 0 else lambda: fact(n - 1, acc * n)

And we run it like this:

result = trampoline(lambda: fact(5000))

Boom. No RecursionError. It just works.

Scene 4: What Just Happened?

Let’s unpack that:

Step 1 — Deferred Evaluation

return lambda: fact(n - 1, acc * n)

We’re not calling fact() — we’re returning a lambda that, when called, will call it. This is called a thunk: a function that defers computation.

Step 2 — Bouncing with the Trampoline

while callable(f):
    f = f()

This loop keeps evaluating the deferred functions, without growing the call stack. Each step is a plain while loop iteration — not a nested call.

Scene 5: Let’s Push It

Let’s prove this works for deep calls. Try computing fact(100000):

print(trampoline(lambda: fact(100000)))

You’ll wait a bit, but you’ll get your answer. No explosion. No recursion depth exceeded. Just a monstrously large number.

Scene 6: Generalizing to Other Recursion

The trampoline pattern works for any tail-recursive function. Let’s build Fibonacci, but in tail-recursive form:

def fib(n, a=0, b=1):
    return a if n == 0 else lambda: fib(n - 1, b, a + b)

print(trampoline(lambda: fib(10000)))

This gives you the 10,000th Fibonacci number — again, stack safely intact.

Scene 7: Caveats and Truth

Before you get too excited, a few honest notes:

This only works if your recursion is tail-recursive.
You must restructure your code to return lambdas instead of recursing directly.
It’s a trick. A useful one, but not a built-in feature.
It’s not faster — just safer for deep recursion.

But in situations where:

You’re building interpreters, compilers, or pipelines
You want elegant functional idioms
You like recursion as a model, but Python says no

…this pattern is gold.

Final Thoughts: Why This Matters

The trampoline pattern isn’t about impressing your colleagues with obscure tricks.

It’s about thinking differently: seeing that you can bend the rules, gently and responsibly, to keep the code you love and make it work in environments that don’t natively support it.

Sometimes, writing beautiful recursive functions feels like an uphill battle in Python. But with trampolines, you get the elegance of recursion and the safety of iteration — without rewriting everything as a for loop.

That’s power. Quiet, lambda-powered power.

Do you like this kind of thinking?

- Follow me on Medium: @gwangjinkim for deep dives on Python, Lisp, system design, and developer thinking, and much more

- Subscribe on Substack: gwangjinkim.substack.com — coming soon with early essays, experiments & newsletters (just getting started).

- Visit my Ghost blog (here): everyhub.org — with hands-on tech tutorials and tools (most of them I cross-post here in medium, but not all of them).

Follow anywhere that fits your style — or all three if you want front-row seats to what’s coming next.