CS Fundamentals

Tail Call Optimization: How Recursive Functions Avoid Stack Overflow

Ordinary recursion allocates a new stack frame for every call. Deep recursion eventually exhausts the stack. Tail call optimization detects when a recursive call is the last thing a function does and reuses the current frame instead, reducing recursion to a loop at the machine level.

Published June 30, 2026

What Is a Tail Call?

A tail call is a function call that occurs in the tail position of a function — meaning the call is the last operation before the function returns, and its return value is returned directly without further computation. When a function calls itself in tail position, it is tail-recursive.

The key condition: the calling function must do nothing with the return value except return it. If it multiplies the result by something, wraps it in a data structure, or adds to it before returning, the call is not in tail position because the current stack frame must survive to perform that post-call computation.

Tail-Recursive vs Non-Tail-Recursive Factorial

The classic factorial is not tail-recursive because the multiplication happens after the recursive call returns:

# NOT tail-recursive: must keep frame to multiply by n
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # n * (...) is post-call work

# factorial(5) creates 5 pending frames:
# 5 * factorial(4)
#     4 * factorial(3)
#         3 * factorial(2)
#             2 * factorial(1)
#                 1 * factorial(0)

The tail-recursive version accumulates the result in an accumulator parameter, so the final call has nothing left to do except return:

# Tail-recursive: accumulator carries the result forward
def factorial_tail(n, acc=1):
    if n == 0:
        return acc
    return factorial_tail(n - 1, acc * n)  # pure tail call

# Call chain: no pending work, each call can replace the previous frame
# factorial_tail(5, 1)
# factorial_tail(4, 5)
# factorial_tail(3, 20)
# factorial_tail(2, 60)
# factorial_tail(1, 120)
# factorial_tail(0, 120)  -> returns 120

The same pattern in JavaScript, which does support TCO in strict mode on V8:

"use strict";
function factTail(n, acc = 1) {
  if (n === 0) return acc;
  return factTail(n - 1, acc * n);  // tail position
}

Why Python Deliberately Skips TCO

Python does not perform tail call optimization, and this is a deliberate design decision by Guido van Rossum. His reasoning: stack traces in Python are deeply informative for debugging. TCO collapses the call stack, making tracebacks misleading or incomplete. Guido also argued that explicit iteration is clearer than recursion in Python, and that TCO encourages a style he considers un-Pythonic. Python's default recursion limit is 1,000 frames (adjustable via sys.setrecursionlimit). Calling factorial_tail(2000) raises RecursionError even though it is technically tail-recursive.

Languages That Guarantee TCO

Scheme: The R5RS and R7RS standards mandate proper tail calls. All tail calls are guaranteed to use constant stack space. Recursive loops in Scheme are idiomatic and efficient.
Erlang and Elixir: The BEAM virtual machine optimizes tail calls. Elixir's recursive functions that use tail position run in constant stack space. Server processes in Elixir use tail-recursive loops with receive as the standard idiom for infinite loops.
Scala with @tailrec: Scala's compiler optimizes tail-recursive functions annotated with @tailrec into loops at the bytecode level. The annotation causes a compile error if the function is not actually tail-recursive, giving you a safety guarantee.
Haskell: Laziness complicates the picture, but strict tail calls are optimized. The common pattern is to use strict accumulator functions with foldl'.
JavaScript (ES6 strict mode): The spec requires TCO, but only Safari's JavaScriptCore implements it fully. V8 and SpiderMonkey removed their TCO implementations citing debugging concerns, the same reason Python cites.

The Trampoline Pattern: TCO Without Language Support

A trampoline is a higher-order function that simulates TCO in any language. Instead of calling the next step directly, each step returns a closure (a "thunk") that represents the next call. The trampoline runs in a loop, repeatedly calling the returned thunk until it gets a non-thunk value back:

def trampoline(f):
    """Run f, bouncing between returned thunks until a plain value."""
    result = f
    while callable(result):
        result = result()
    return result

def fact_tramp(n, acc=1):
    if n == 0:
        return acc
    return lambda: fact_tramp(n - 1, acc * n)  # return thunk, not call

print(trampoline(fact_tramp(10_000)))  # works without RecursionError

The trampoline loop runs on the Python call stack with only one active frame at a time. Each thunk delays the next step until the loop invokes it. The trade-off is slightly more overhead per step and less readable code than direct recursion.

When to Reach for Iteration Instead

In Python and most mainstream languages without TCO, convert deep recursion to an explicit loop when you know inputs can be large. Iteration is always available, never overflows the stack, and in Python it is faster due to lower per-call overhead. Save recursion for cases where the recursive structure makes the algorithm significantly clearer — tree traversal, parsing, divide-and-conquer — and where depth is bounded by problem structure (e.g., a balanced binary tree of depth 20 is fine even in Python).