Tail Recursion

The previous lesson showed that, in linear recursion, every call carries a frame cost — a cost that is not always unavoidable. Under a specific form, no reason remains to keep the frame.

The subject of this lesson is that form and its equivalence to a loop.

Tail Position

A call is in tail position if it is the last operation the function performs: no work remains once it returns, and the returned value is passed directly outward.

The factorial from the previous lesson does not satisfy this condition:

def factorial(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial(n - 1)      # the multiplication happens AFTER the call returns

In the last line, the recursive call is not the last operation; its result will be multiplied by n. The calling frame must therefore wait until the inner call returns, holding the value of n and where to return to.

The tail form of the same computation moves the work not yet done into an accumulator parameter:

def factorial_tail(n: int, accumulator: int = 1) -> int:
    """Computes the value of n! in tail-recursive form."""
    if n <= 1:
        return accumulator                       # base case: return the accumulator
    return factorial_tail(n - 1, n * accumulator)   # last operation: the call itself

print(factorial_tail(5))     # 120
print(factorial(5))          # 120  — the same result

The multiplication now happens before the call, while the argument is prepared. Because no work remains once the call returns, there is no need to preserve the calling frame.

Why the Frame Is Not Needed

A frame is kept for two things: the return address and local values. In tail position, since the inner call’s return value passes directly outward, the caller’s return address and the inner call’s are the same. Local values are no longer needed either; all have moved into the arguments.

Consequently, instead of opening a new frame, the existing frame can be reused — a transformation called tail call optimization. When applied, the stack does not grow regardless of recursion depth.

Language Support Is Not Universal

Whether this optimization is performed depends on the language and its implementation, part of the language’s definition rather than a detail of speed. Some languages guarantee it, allowing deep tail recursion to be written safely; some do not apply it at all.

Python is among the languages that do not apply it; even a function written in tail form hits the recursion limit as the depth increases:

# factorial_tail(5000)  -> recursion limit exceeded error

The rationale is a design choice: preserved frames keep the error trace complete and debugging easier, at the cost that deep recursion cannot be used.

The conclusion: writing in tail form does not, by itself, guarantee depth. Whether the language performs this optimization must be known.

In runtimes where the recursion limit can be raised, this appears to be a solution, but is not: the limit exists to warn before the actual stack space runs out, and raising it can turn a controlled error into an uncontrolled crash. The correct solution is taking a depth that grows with the data out of recursion entirely.

Equivalence to a Loop

The relationship between tail recursion and a loop is mechanical: accumulator parameters correspond to loop variables, the reduction step to updates, and the base case to the loop condition.

def factorial_loop(n: int) -> int:
    accumulator = 1
    while n > 1:                 # the negation of the base case
        accumulator = n * accumulator    # the arguments of the recursive call
        n = n - 1
    return accumulator

print(factorial_loop(5))       # 120

All three versions produce the same value; the difference lies only in syntax and stack behavior — the loop version uses a single frame and recognizes no depth limit.

The correspondences map one by one: the accumulator to the loop variable, the negation of the base case to the loop condition, the recursive call’s arguments to updates in the body. This mapping also gives the recursive counterpart of the loop invariant — the meaning the accumulator carries at every call is precisely the loop invariant.

This equivalence also explains what tail call optimization does: the compiler applies the transformation automatically, and the resulting code is the loop version’s code.

Converting Non-Tail Recursion to a Loop

Every recursive solution can be converted to a loop, but if the call is not in tail position, the conversion is not mechanical. The work remaining after the call must be stored somewhere, and once the frame is removed, that responsibility passes to the program: the stack is maintained by hand.

Traversing a tree-like structure is the typical example of this. The solution below flattens nested lists without using recursion:

def flatten(data: list) -> list[int]:
    """Reduces nested lists to a single level; uses no recursion."""
    result = []
    pending = [data]                       # parts still to process
    while pending:
        part = pending.pop()
        if isinstance(part, list):
            pending.extend(reversed(part))   # append in reverse to preserve order
        else:
            result.append(part)
    return result

print(flatten([1, [2, [3, 4]], 5]))    # [1, 2, 3, 4, 5]

The pending list here does the work the call stack does in the recursive version, holding the parts not yet processed. The code grows longer and readability drops; in exchange, the depth limit disappears and memory use becomes controllable.

The criterion is clear: if the depth grows without bound with the input, and the language does not perform tail call optimization, the stack is maintained by hand.

Which Form, and When

The choice among the three forms depends on context.

Direct recursion is the closest to the problem definition and the easiest to read. It is preferred when the depth is small and bounded.

Tail form is the right choice for deep repetition in languages that guarantee the optimization. Adding an accumulator parameter drops readability somewhat, so the accumulator-carrying version is usually placed in a helper function, keeping the outer interface simple:

def factorial_clean(n: int) -> int:
    """The outer interface is simple; the accumulator detail is hidden."""
    def helper(k: int, accumulator: int) -> int:
        if k <= 1:
            return accumulator
        return helper(k - 1, k * accumulator)
    return helper(n, 1)

print(factorial_clean(5))       # 120

This style directly applies the inner-function idea from the scope lesson: the helper is not visible from outside, and it makes sense only within its own context.

A loop is the safe choice in languages without an optimization guarantee, and where depth grows with the input.

This threefold choice also explains language design preferences. Languages prioritizing immutability treat recursion, rather than rebinding a loop variable, as the primary tool of repetition; there, tail call optimization is a necessity, not a convenience. Languages treating the loop as primary suffer no deficiency from skipping the optimization — writing the same task with a loop is already expected. Which path a language chooses determines what its code looks like; this relationship is the central idea of the next topic.

Summary

• A call is in tail position if it is the function’s last operation; no work remains after it returns.
• Direct recursion is converted to tail form by moving the work not yet done into an accumulator parameter.
• In tail position, the calling frame can be reused; this transformation is called tail call optimization.
• Whether the optimization is applied depends on the language and is not universal; writing in tail form alone does not guarantee depth.
• The conversion between tail recursion and a loop is mechanical: accumulators become the loop variable, the base case becomes the loop condition.
• The accumulator detail is hidden from the outer interface by moving it into an inner helper function.

Next Step

This topic established the function as a tool of abstraction: work is named, input and output are bound to a contract, and scope is isolated. The function is not the only tool of abstraction. The next topic will compare three separate approaches to organizing programs — structured, object-oriented, and functional — and solve the same problem with each of them.