Course contentsShow
← Computer Science
Lesson 227 of 2,8725. Functions and ModularityFree lesson

Tail Recursion

Identify tail-recursive functions where the recursive call is the final operation, enabling optimization.

Tail Recursion

What you'll learn: You'll discover a special form of recursion where the recursive call is the very last thing a function does, making it eligible for powerful optimizations.


What Makes Recursion "Tail"?

A recursive function is tail-recursive when the recursive call is the final operation before returning—nothing happens after it comes back. There's no pending work like arithmetic, comparisons, or combining results with other values.

Think of it like a relay race where each runner immediately hands off the baton and walks away. They don't wait to do anything with the result—they're done. In contrast, regular recursion is like waiting for the runner to come back, then adding your own lap time to theirs.

Spotting Tail Recursion

Consider a countdown function:

Tail-recursive version:

def countdown(n):
    if n == 0:
        return
    print(n)
    countdown(n - 1)  # Last operation—nothing after this

Non-tail-recursive version:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)  # Multiplication happens AFTER the call returns

In the factorial, after factorial(n - 1) returns, the function still has to multiply by n. That pending work means it's not tail-recursive.

Why It Matters

When a compiler or interpreter detects tail recursion, it can reuse the same stack frame instead of creating new ones. This optimization (called tail call optimization) prevents stack overflow and makes recursion as efficient as loops.

Key Takeaway: Tail recursion occurs when the recursive call is the absolute last operation with no pending work, enabling compilers to optimize it into an efficient loop-like structure.