Introduction

Recursion is the technique of solving a problem by having a function call itself on a smaller version of the same problem. In Python, recursion is easy to write, but it only becomes understandable once you clearly separate the base case from the recursive case.

The Two Required Parts Of Recursion

Every recursive function needs two things:

• a base case that stops the recursion
• a recursive case that moves the problem toward that base case

Without a base case, recursion never ends. Without progress toward the base case, recursion also never ends.

A simple factorial example shows both parts clearly.

1def factorial(n: int) -> int:
2    if n == 0:
3        return 1
4    return n * factorial(n - 1)
5
6
7print(factorial(5))

Here:

• 'n == 0 is the base case'
• 'factorial(n - 1) is the recursive call'

What Actually Happens On The Call Stack

When you call factorial(4), Python does not compute the answer all at once. It builds a stack of pending work.

The calls look like this conceptually:

• 'factorial(4) needs 4 * factorial(3)'
• 'factorial(3) needs 3 * factorial(2)'
• 'factorial(2) needs 2 * factorial(1)'
• 'factorial(1) needs 1 * factorial(0)'
• 'factorial(0) returns 1'

Then the calls unwind:

• 'factorial(1) returns 1 * 1 = 1'
• 'factorial(2) returns 2 * 1 = 2'
• 'factorial(3) returns 3 * 2 = 6'
• 'factorial(4) returns 4 * 6 = 24'

That "go down, then unwind" pattern is the mental model that makes recursion easier to follow.

A Trace Function Makes It Visible

You can instrument a recursive function to see the flow.

1def factorial_trace(n: int, depth: int = 0) -> int:
2    indent = "  " * depth
3    print(f"{indent}call factorial({n})")
4
5    if n == 0:
6        print(f"{indent}return 1")
7        return 1
8
9    result = n * factorial_trace(n - 1, depth + 1)
10    print(f"{indent}return {result}")
11    return result
12
13
14factorial_trace(4)

This kind of tracing is one of the best ways to learn recursion because it shows the nested structure explicitly.

Recursion Works Best For Recursive Data Or Structure

Some problems are naturally recursive:

• traversing trees
• walking nested directories
• divide-and-conquer algorithms such as merge sort
• mathematical definitions such as factorial or Fibonacci

For example, summing a list recursively is simple to read:

1def recursive_sum(values: list[int]) -> int:
2    if not values:
3        return 0
4    return values[0] + recursive_sum(values[1:])
5
6
7print(recursive_sum([1, 2, 3, 4]))

This is not always the most efficient Python implementation, but it expresses the recursive idea clearly.

Recursion Versus Iteration

Not every problem that can be solved recursively should be solved recursively in Python.

For example, factorial can also be written iteratively:

1def factorial_iterative(n: int) -> int:
2    result = 1
3    for i in range(2, n + 1):
4        result *= i
5    return result

Iteration is often more memory-efficient in Python because recursive calls consume stack frames. That means the best recursive explanation and the best production implementation are not always the same thing.

Recursion Depth In Python

Python does not optimize tail recursion, and it has a recursion depth limit. Deep recursive calls can raise RecursionError.

# This kind of code can eventually fail if the depth gets too large.

So recursion is great for clarity and for naturally recursive structures, but it is not always appropriate for extremely deep input.

Common Pitfalls

The most common mistake is forgetting the base case or writing a base case that is never reached.

Another mistake is making the recursive call without shrinking the problem. If the input does not get smaller, the function will recurse forever.

Developers also often misunderstand when the real work happens. In many recursive functions, the final answer is assembled while the call stack unwinds, not when the calls are going deeper.

Finally, recursion in Python is not automatically elegant if the problem is fundamentally iterative. Use it when it makes the structure clearer, not just because it looks clever.

Summary

• Recursion means a function solves a problem by calling itself on a smaller case.
• Every recursive function needs a base case and a recursive case.
• The call stack grows during descent and resolves during unwinding.
• Tracing the function call depth is a practical way to understand recursion.
• In Python, recursion is useful, but deep recursion can hit stack limits.