Course contentsShow
← Computer Science
Lesson 872 of 2,87220. Recursion Patterns and TechniquesFree lesson

Tail Recursion Optimization

Write tail-recursive functions where the recursive call is the last operation, enabling compiler optimization.

Tail Recursion Optimization

What you'll learn: How to write recursive functions in a way that allows compilers to optimize them into efficient loops.

The Core Idea

Tail recursion happens when a recursive call is the very last operation a function performs—nothing else happens after it returns. When written this way, smart compilers can transform your recursion into a loop automatically, eliminating the risk of stack overflow and making it as efficient as iteration.

Think of it like a relay race: in normal recursion, each runner waits at the finish line to hand something back to the previous runner (building up a crowd). In tail recursion, each runner simply tags the next one and leaves immediately—no waiting, no crowd buildup.

Writing Tail-Recursive Functions

The key is using accumulators (as you learned in the previous lesson) to carry results forward instead of doing work after the recursive call returns.

Not tail-recursive (work happens after the call):

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)  # multiplication AFTER return

Tail-recursive (nothing happens after the call):

def factorial(n, accumulator=1):
    if n <= 1:
        return accumulator
    return factorial(n - 1, n * accumulator)  # result passed forward

In the second version, the recursive call is the absolute last thing executed—no multiplication waits for the result. Compilers can recognize this pattern and reuse the same stack frame instead of creating new ones.

Why It Matters

Languages like Scheme guarantee tail-call optimization. Python and Java don't optimize it automatically, but understanding the pattern still helps you write clearer code and manually convert recursion to iteration when needed.

Key Takeaway: Tail recursion places the recursive call as the final action with no pending operations, enabling compilers to optimize recursive functions into loops and avoid stack overflow.