Tail Recursion Explained: Why Python Still Hits the Recursion Limit

A recursive function that sums a list of a hundred thousand numbers crashes in Python with RecursionError, while the same function in Scheme runs in constant stack space. The difference is tail call elimination: when the recursive call is the very last thing a function does, a language can reuse the caller's frame instead of stacking a new one. Python does not. Knowing what a tail call is, why Python keeps every frame anyway, and how to rewrite the function as a loop is a standard recursion follow-up, and the rewrite is mechanical once you see it.

The problem it solves

Every function call pushes a frame holding its arguments, locals and the place to return to. A recursion n levels deep holds n frames at once. In CPython the default limit is 1,000 frames (as of September 2026), and raising it with sys.setrecursionlimit only moves the crash: past a point the interpreter's own C stack overflows and the process dies instead of raising a clean error.

So any recursion whose depth grows with the input, such as walking a long linked list, summing a range, or descending a degenerate tree, is a bug waiting for a large input. The question is which recursions can be turned into loops cheaply, and how.

The intuition

Compare two ways to sum 1..n.

return n + total(n - 1) is not a tail call. After the inner call returns, this frame still has work to do: the addition. Its n must be kept alive until then.

return total(n - 1, acc + n) is a tail call. The addition has already happened and been passed down in the accumulator. When the inner call returns, this frame just hands the result back unchanged. It has no work left, and its locals are never read again.

A language with tail call elimination notices that and reuses the frame, so the recursion runs like a loop. Scheme requires it by its standard; Scala's @tailrec and Kotlin's tailrec turn self tail calls into loops at compile time. Python's designers declined to add it, partly to keep complete tracebacks, so in CPython a tail call costs a frame like any other call.

The fix is to do the translation yourself. The accumulator parameter becomes a local variable, the tail call becomes an update of the parameters, and the base case becomes the loop's exit. That is exactly the step the lesson calls mechanical. For a recursion that is not in tail form, the first move is to introduce an accumulator that carries the pending work down; for one that branches, like a tree walk, the loop needs an explicit stack instead of a single accumulator.

Watch it run

The animation runs total(4) twice. First as a recursion: total(n, acc) adds n to the accumulator and calls itself, and the call is the last thing it does. Frame 1 is created just to pass 4 along; it has no work waiting for a result. Frames 2, 3 and 4 follow, carrying 7, 9 and 10. Then the base case returns 10, already the final answer. Every frame now returns the same number unchanged: five frames held open to carry one integer. Then the loop version: one frame, and the accumulator is an ordinary variable. acc and n are just reassigned, n=4 acc=0, then n=3 acc=4, and so on; nothing is pushed, so nothing has to be unwound. It ends on the same answer, 10, at a constant depth of one, where no RecursionError is possible.

The code

The lesson's pair. Both agree on small inputs; only the loop survives a large one:

import inspect
import sys

def total(n, acc=0):
    if n == 0:
        return acc
    return total(n - 1, acc + n)           # tail call: nothing left to do afterwards

def total_loop(n):
    acc = 0
    while n:                               # the same function with the frames taken out
        acc, n = acc + n, n - 1
    return acc

print(total(4), total_loop(4))             # 10 10
print(sys.getrecursionlimit())             # 1000
try:
    total(100_000)
except RecursionError:
    print("RecursionError")                # RecursionError
print(total_loop(100_000))                 # 5000050000

Proof that the tail call still keeps its frames in CPython: at the base case, the stack is exactly one frame deeper per call:

def depth_at_base(n, acc=0):
    if n == 0:
        return len(inspect.stack())
    return depth_at_base(n - 1, acc + n)

print(depth_at_base(300) - depth_at_base(0))   # 300

Turning a non-tail recursion into tail form. In fact, the multiplication waits for the call; moving it into an accumulator makes the call the last step, and the loop follows directly:

def fact(n):
    return 1 if n == 0 else n * fact(n - 1)             # the multiply waits: not a tail call

def fact_acc(n, acc=1):
    return acc if n == 0 else fact_acc(n - 1, acc * n)  # tail call: the multiply went into acc

def fact_loop(n):
    acc = 1
    while n:
        acc, n = acc * n, n - 1
    return acc

print(fact(10), fact_acc(10), fact_loop(10))   # 3628800 3628800 3628800

When you want to keep the recursive shape, a trampoline gets the same effect: the function returns the next call as a zero-argument function instead of making it, and a loop keeps calling until a value comes back. It even handles mutual recursion:

def trampoline(result):
    while callable(result):                # bounce until a plain value comes back
        result = result()
    return result

def total_t(n, acc=0):
    return acc if n == 0 else (lambda: total_t(n - 1, acc + n))

def is_even(n):
    return True if n == 0 else (lambda: is_odd(n - 1))

def is_odd(n):
    return False if n == 0 else (lambda: is_even(n - 1))

print(trampoline(total_t(100_000)))        # 5000050000
print(trampoline(is_even(100_001)))        # False

A recursion that branches has no single accumulator; the loop version keeps an explicit stack instead. A 5,001-level chain that would break the recursive walk is fine:

def walk(tree):
    value, children = tree                 # a tree is (value, [children])
    return value + sum(walk(c) for c in children)

def walk_stack(tree):
    acc, stack = 0, [tree]
    while stack:
        value, children = stack.pop()
        acc += value
        stack.extend(children)
    return acc

deep = (1, [])
for _ in range(5_000):
    deep = (1, [deep])
print(walk_stack(deep))                    # 5001

Checked on 500 seeded random inputs: every recursive, loop and trampolined version must agree with a closed form or the standard library, and the two tree walks must agree on random trees:

import math
import random

def gcd_tail(a, b):
    return a if b == 0 else gcd_tail(b, a % b)

def gcd_loop(a, b):
    while b:
        a, b = b, a % b
    return a

def random_tree(rng, size):
    if size == 1:
        return (rng.randint(-9, 9), [])
    kids, left = [], size - 1
    while left:
        k = rng.randint(1, left)
        kids.append(random_tree(rng, k))
        left -= k
    return (rng.randint(-9, 9), kids)

random.seed(25)
ok = True
for _ in range(500):
    n = random.randint(0, 900)
    ok &= total(n) == total_loop(n) == trampoline(total_t(n)) == n * (n + 1) // 2
    m = random.randint(0, 60)
    ok &= fact(m) == fact_acc(m) == fact_loop(m) == math.factorial(m)
    a, b = random.randint(0, 10**6), random.randint(0, 10**6)
    ok &= gcd_tail(a, b) == gcd_loop(a, b) == math.gcd(a, b)
    k = random.randint(0, 50)
    ok &= trampoline(is_even(k)) == (k % 2 == 0)
    t = random_tree(random, random.randint(1, 40))
    ok &= walk(t) == walk_stack(t)
print(ok)                                  # True

The complexity

• Time: unchanged by any of these rewrites; total is O(n) in every form.
• Stack space: O(n) for the recursive version in CPython, tail call or not. O(1) for the loop and the trampoline.
• Explicit stack: a branching walk still needs O(depth) memory, but on the heap, where a list of a million entries is ordinary.

Where it goes wrong

• Assuming Python optimises tail calls. It does not; a tail-recursive function has the same depth limit as any other.
• Calling n + f(n - 1) a tail call. The addition after the call is pending work.
• Raising the recursion limit as the fix. It trades a clean exception for a possible hard crash.
• Returning the call instead of a thunk. A trampoline only works if the function returns lambda: f(...), not f(...).
• Forcing everything into tail form. A balanced tree walk is only O(log n) deep; recursion is fine there.

When it shows up in interviews

It comes up as a follow-up: "your recursive solution works; what happens on a list of a million nodes?" The expected answer is the depth limit, the accumulator rewrite, and the loop. It also appears as "convert this recursion to iteration", where the explicit stack is the general answer, and as a question about why memoization can hit the recursion limit where tabulation does not.

How to say it in an interview

"A call is in tail position when its result is returned unchanged, so the caller's frame has nothing left to do. Some languages reuse the frame; CPython does not, so a tail-recursive function still uses O(n) stack and hits the default limit of about a thousand frames. The rewrite is mechanical: the accumulator becomes a local, the tail call becomes reassigning the parameters, and the base case becomes the loop condition. If the recursion branches, I use an explicit stack instead."