juniorRecursion

What is tail recursion and why does it matter?

Updated Feb 20, 2026

Short answer

A recursive call is in tail position when it is the very last operation in the function — its result is returned directly, with no pending work afterwards. That matters because the current stack frame is no longer needed once the call is made, so a compiler can reuse it instead of pushing a new one. This turns recursion of depth n from O(n) stack space into O(1), eliminating stack overflow.

Deep explanation

The distinction hinges on whether anything remains to be done after the recursive call returns.

Python
def factorial(n):                 # NOT tail recursive
    if n <= 1:
        return 1
    return n * factorial(n - 1)   # must multiply AFTER the call returns


def factorial_tail(n, acc=1):     # tail recursive
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)   # nothing pending

In the first, the frame must survive the recursive call because it still holds n for the multiplication. In the second, the multiplication happens before the call, and the accumulator carries the partial result down. Once the call is made, the frame holds nothing of value.

That is the enabling condition for tail-call optimisation: rather than pushing a frame, the compiler overwrites the current one and jumps. The recursion becomes a loop, and depth becomes irrelevant.

The accumulator-passing transformation shown above is the standard technique for converting a non-tail-recursive function into a tail-recursive one.

Language support is the catch, and interviewers probe it. Scheme mandates TCO. Most functional languages and many JVM/BEAM languages provide it. Notably, CPython does not and by design will not — Guido van Rossum has argued that losing stack traces harms debuggability more than the optimisation helps. Java does not either. JavaScript engines mostly do not, despite ES6 specifying proper tail calls — only JavaScriptCore shipped it.

So in Python or Java, writing a function in tail-recursive style yields no space benefit whatsoever; factorial_tail(100000) still overflows. There the practical move is to write the loop directly:

Python
def factorial_iter(n):
    acc = 1
    for i in range(2, n + 1):
        acc *= i
    return acc

The concept still earns its place: recognising tail position tells you which recursive functions convert mechanically into loops, which is exactly the refactor a deep recursion needs.

Real-world example

A directory walker recursing into a deeply nested tree hits Python's default 1000-frame limit on a path nested ~1200 deep.

Python
# Overflows on deep trees — and rewriting it tail-recursively would NOT help in Python.
def walk(path, found=None):
    found = found if found is not None else []
    for entry in listdir(path):
        if isdir(entry):
            walk(entry, found)      # recursive descent
        else:
            found.append(entry)
    return found

Because CPython performs no TCO, the fix is an explicit stack — which is precisely what TCO would have done for you, done by hand:

Python
def walk_iter(root):
    found, stack = [], [root]
    while stack:                    # the call stack, now on the heap
        path = stack.pop()
        for entry in listdir(path):
            (stack if isdir(entry) else found).append(entry)
    return found

Heap-allocated, so it is bounded by memory rather than by the recursion limit — it handles trees of any depth.

Common mistakes

  • - Assuming any recursive call in the return statement is a tail call
  • `return n * f(n-1)` is not, because the multiplication is still pending.
  • - Writing tail-recursive code in Python, Java, or most JavaScript engines and expecting stack safety — those runtimes do not optimise tail calls.
  • - Believing `return f(x) + 0` or wrapping the call in a `try` block preserves tail position
  • any surrounding operation or handler defeats it.
  • - Raising the recursion limit with `sys.setrecursionlimit` instead of restructuring, which trades a clean exception for a hard interpreter crash.
  • - Forgetting the base case, or writing one that some inputs never reach — negative arguments to a `n == 0` guard, for instance.
  • - Reaching for recursion where a loop is clearer
  • tail recursion and iteration are equivalent in power, and the loop is usually more readable in imperative languages.

Follow-up questions

  • Why does CPython deliberately omit tail-call optimisation?
  • How do you convert a non-tail-recursive function to a tail-recursive one?
  • What is mutual recursion and can it be tail-optimised?
  • When is recursion preferable to iteration even without TCO?

More Recursion interview questions

View all →