Recursion

Recursion solves a problem by reducing it to smaller versions of the same problem. A recursive function calls itself until it reaches a case that no longer needs another call.

Recursion is common in trees, depth-first search, divide and conquer, and many dynamic programming solutions.

Core Idea

A recursive solution needs two parts: a base case and a recursive case. The base case stops the recursion. The recursive case makes progress toward the base case.

Without a base case, or without progress toward it, recursion does not terminate.

A good recursive function should have a clear meaning. For example, factorial(n) means “the product of all integers from 1 through n.” Once that meaning is clear, the recursive case says how to express the answer using a smaller answer.

Function Contract

factorial(n) expects a non-negative integer n.

It returns the product of every integer from 1 through n, with factorial(0) == 1. The example does not handle negative input because negative values would move away from the base case.

Python Example

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

The base case is n == 0. The recursive case reduces n by one.

Call Trace

For factorial(4), the calls expand like this:

factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)

The base case returns 1, and then the waiting calls finish in reverse order.

This reverse return order is why recursion behaves like a stack.

Complexity of the Example

factorial(n) makes one recursive call for each value from n down to 0, so its time complexity is O(n).

The call stack also grows to depth n, so the extra space is O(n). This stack space is separate from ordinary variables in one call.

Designing Recursive Code

Use this checklist:

1. State what the function returns.
2. Identify the smallest input that can be answered directly.
3. Write the recursive case using smaller inputs.
4. Make sure every recursive call moves toward a base case.

For tree problems, the smaller input is often a child subtree. For array problems, it may be a smaller range.

Failure Example

If factorial received -1, the recursive call would move to -2, then -3, and never reach the base case 0. Recursive code needs an input contract or an explicit guard for values outside the intended domain.

Common Confusions

Recursion is not magic. Each call has its own local variables and waits for smaller calls to return.

Python has a recursion limit. Very deep recursion can raise RecursionError, even when the algorithm idea is correct.

Another common mistake is writing a recursive call but ignoring its return value. If the smaller problem’s answer matters, the caller must use it.

When To Use It

Use recursion when the problem naturally splits into smaller similar problems, especially with trees, nested structures, backtracking choices, and divide-and-conquer algorithms.

Avoid recursion when a simple loop expresses the process more clearly or when input depth may exceed Python’s recursion limit.

The Main Point

Recursion is a way to define a solution through smaller versions of the same problem. The base case and progress toward it are the difference between a solution and an infinite call chain.