A function is recursive when solving one problem can involve calling the same function on a smaller or simpler version of that problem.

A useful recursive definition has two parts: one or more base cases that stop immediately, and a recursive case that reduces the problem toward a base case.

Example: factorial

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

The calls build up as

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

and then return in the opposite order.

Progress toward termination

A recursive definition that never reaches a base case continues creating calls until some external limit stops it. Correct recursion therefore requires a decreasing measure or another argument showing that the base case will eventually be reached.

Recursion and iteration

Many recursive procedures can be rewritten as loops with explicit state, and many iterative procedures can be expressed recursively. The useful representation depends on the problem.

Recursive structure is especially natural for nested data such as trees, divide-and-conquer algorithms and mathematical definitions that refer to smaller instances of themselves.