---
title: 'Tail Recursion'
source: 'https://academia.sh/en/courses/programming-fundamentals/tail-recursion'
course: 'Programming Fundamentals'
language: en
updated: '2026-08-17T18:08:25+00:00'
license: 'CC BY-SA 4.0'
---

# Tail Recursion

The call in tail position, transformation with an accumulator parameter, frame reuse, and equivalence to a loop.

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:

```python
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**:

```python
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:

```python
# 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.

```python
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:

```python
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:

```python
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.