Recursion and Iterative Alternatives

A Function That Calls Itself

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every correct recursive function has two parts: a base case that stops the recursion (a smallest input answered directly, without recursing), and a recursive case that reduces the problem toward the base case.

The classic example is factorial: $n! = n \times (n-1)!$, with base case $0! = 1$.

def factorial(n):
    if n == 0:        # base case
        return 1
    return n * factorial(n - 1)   # recursive case

Each call waits for the smaller call to finish, so calls stack up: factorial(3) waits for factorial(2), which waits for factorial(1), which waits for factorial(0) = 1, and then the results multiply back up. This chain lives on the call stack, and if recursion never reaches the base case — an infinite recursion — the stack grows until it overflows (a stack overflow).

Anything recursive can also be written iteratively with a loop, and vice versa. Recursion often expresses naturally-recursive problems (trees, divide-and-conquer) more clearly, but each call has overhead and stack cost; iteration is usually more memory-efficient for simple repetition. The choice is about clarity and cost, not capability.

Common pitfall: forgetting the base case, or writing a recursive case that does not actually move toward it. Either causes infinite recursion and a stack overflow. Every recursive function must have a reachable base case, and each recursive call must make the problem strictly smaller.

A recursion call stack drawn as nested frames descending factorial→→→=1, then an accent wave multiplying results back up the stack: 1, 1, 2, 6 — the descend-then-combine shape of recursion.

$$n! = n \times (n-1)!, \;\; 0! = 1$$