Recursion

If a function can call another function inside its body, it can call itself as well. This is permitted by definition, and it is called recursion.

This idea, which appears circular at first glance, becomes clear once the call stack is understood: each call has its own frame, so multiple calls to the same function can exist at once, each with independent variables.

Two Required Parts

Every recursive definition consists of two parts:

Base case: The smallest case, answered directly without recursion.

Reduction step: The step that transforms the problem into a smaller instance of the same problem.

If either part is missing, the solution does not work. Without a base case, the calls continue indefinitely; if the reduction does not make the problem smaller, the base case is never reached.

def factorial(n: int) -> int:
    """Computes the value of n!. n must not be negative."""
    if n < 0:
        raise ValueError("negative value")
    if n <= 1:              # base case
        return 1
    return n * factorial(n - 1)     # reduction: n decreases to n - 1

print(factorial(5))        # 120
print(factorial(0))        # 1

Writing the base case as n <= 1 gives the correct answer for both $0$ and $1$, and guarantees that every non-negative input reaches the base case.

Expansion on the Stack

Executing the call factorial(4) proceeds as frames accumulate on top of one another and are then resolved in reverse order:

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))          ← base case reached
= 4 * (3 * 2)
= 4 * 6
= 24

The lines going upward show the calls expanding, and the lines going downward show the returns being combined. At the deepest point, four frames are on the stack at the same time; each has its own value of n.

This is the clearest example of the frame model established in the previous course: n is not a single memory cell; it exists separately in the frame of each call.

Infinite Recursion

When the base case is forgotten, or when the reduction does not make the problem smaller, calls accumulate and the stack runs out.

def broken(n: int) -> int:
    return n * broken(n - 1)     # no base case

# broken(5)  -> recursion limit exceeded error

This behavior was defined in the memory layout lesson of the previous course: every call adds a frame, none of them return, and the space allocated for the stack runs out. In languages with a runtime guard, a controlled error is raised; in those without one, the process is terminated.

The error message typically contains the same function name hundreds of times — this is the distinctive signature of infinite recursion.

Naturally Recursive Problems

Recursion is the natural solution when the problem itself is defined recursively. The sum of a list of measurements can be defined this way: the sum of an empty list is zero; the sum of a non-empty list is its first element plus the sum of the rest.

def total(measurements: list[int]) -> int:
    if not measurements:                        # base case: empty list
        return 0
    return measurements[0] + total(measurements[1:])   # reduction: one fewer element

print(total([12, 18, 7]))     # 37
print(total([]))              # 0

This solution is a direct translation of the definition; it is easy to read. In exchange, it copies the rest of the list on every call and opens as many frames as there are elements — a loop performing the same task works with a single frame and no copying.

Where recursion is genuinely superior is in problems where the data itself branches: traversing tree structures, scanning directories with their subdirectories, divide-and-conquer algorithms. These structures are the subject of the Data Structures and Algorithms courses; most solutions there are written recursively.

Cost and Repeated Computation

Recursion has two costs: memory per frame and extra processing per call. A third, more insidious cost is the same computation being repeated.

The direct recursive definition of the Fibonacci sequence is the canonical example of this.

def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))          # 55

While computing fib(5), fib(3) is computed twice and fib(2) three times. As the input grows, the number of repetitions grows exponentially; computing fib(30) makes more than a million calls.

The solution is to store the computed values:

def fib_memoized(n: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:                 # already computed, do not recompute
        return memo[n]
    memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    return memo[n]

print(fib_memoized(30))             # 832040

The precondition for memoization is that the function always produces the same result for the same input; the result of a function that depends on state beyond its input cannot be stored this way. This technique is called memoization, and it is the foundation of dynamic programming; it is treated in its general form in the Advanced Algorithms course. The lesson here is that recursion gives the structure of a solution but does not bring efficiency on its own.

Mutual Recursion

Recursion is not limited to a function calling itself directly. Two functions calling each other can also form a recursive structure; this is called mutual recursion.

def is_even(n: int) -> bool:
    if n == 0:
        return True
    return is_odd(n - 1)

def is_odd(n: int) -> bool:
    if n == 0:
        return False
    return is_even(n - 1)

print(is_even(4), is_odd(4))     # True False

This example exists to illustrate the concept; the same question is answered in a single step with the remainder operator. The real use of mutual recursion is in structures where interdependent definitions are naturally mutual — parsers processing grammar rules are the typical example: an expression definition refers to a term definition, which refers back to expression.

The base case rule applies here as well, but it becomes harder to verify: the guarantee of termination must be found not in a single function but across the entire chain of calls.

Recursion or Loop

The criteria for choosing:

Criterion	Recursion	Loop
The problem definition branches	Natural	Requires manual stack management
Progress is linear	Pays a frame cost	Cheaper
Depth grows with the input	Risk of hitting the stack limit	No limit
Readability	Close to the definition	Close to the steps

The general rule: use recursion if the problem is defined recursively, use a loop if the repetition is linear. Every recursive solution can be converted to a loop; the conversion may require maintaining a stack manually.

Summary

• Recursion is a function calling itself; because each call has its own frame, the variables do not mix.
• Every recursive definition contains a base case and a reduction step; if either is missing, the solution does not work.
• Calls accumulate on the stack, expansion stops at the base case, and the returns are combined in reverse order.
• Infinite recursion exhausts the stack; its signature is the repeated function name in the error message.
• Recursion is natural for branching structures; a loop is cheaper for linear repetition.
• Recomputing the same subproblem can produce exponential cost; memoization removes this repetition.

Next Step

In linear recursion, the frame cost appears unavoidable. The situation changes, however, when the call is the last operation in the body: opening a new frame is no longer necessary. The next lesson takes up this special form — tail recursion — and its equivalence to a loop.