2 Recursion

1. Core model and design

The central idea

Recursion solves a problem by applying the same method to a smaller or simpler instance of that problem. The approach works when each call makes measurable progress toward a stopping condition.

A recursive solution has two essential parts:

• A Base case gives an answer directly and stops the process.

• A Recursive case reduces the problem and calls the function again.

For example, factorial follows the definition

with the base case

To evaluate $4!$, the calls reduce the argument until the base case is reached, then return through the pending multiplications:

The same pattern appears in nested expressions, directory hierarchies, trees, linked structures, and divide-and-conquer algorithms.

A reliable design process

1. Define precisely what one call must return.

2. Identify the smallest valid inputs and define their direct answers.

3. Express the original problem using one or more smaller instances of the same problem.

4. Verify that every recursive call moves closer to a base case.

5. Combine the returned results correctly.

6. Estimate running time and maximum call depth.

Takeaway: Recursion is not merely self-calling code; it is a reduction from a well-defined problem to smaller instances with a guaranteed stopping point.

2. Base cases, progress, and execution

Example: processing an array segment

Suppose a function must sum the portion of an array beginning at index $i$. Define the subproblem as “sum the elements from index $i$ through the end.” If $i$ reaches the array length, no elements remain, so the answer is zero. Otherwise, add the current element to the result for the remaining segment:

with

This definition is correct because each call removes one element from the unresolved portion. The empty remaining segment is a complete and reachable base case.

Reachability and completeness

A base case should satisfy three tests:

• Reachable: recursive calls can actually arrive at it.

• Correct: it gives the right answer for the smallest subproblem.

• Complete: every valid input eventually reduces to one or more covered base cases.

Consider a countdown. If a positive input is passed unchanged to the next call, the input never gets closer to zero and the function does not terminate. Replacing the input with one less than its current value establishes progress.

For recursive tree algorithms, an empty tree commonly needs its own base case. Omitting it can cause invalid access or prevent termination.

Tracing the call stack

The Call stack stores a frame for each active call. For a countdown beginning at $3$, frames are added in this order: $3$, then $2$, then $1$, and finally $0$. Once the call for $0$ returns, the frames are removed in reverse order, so work after the recursive call runs for $1$, then $2$, then $3$.

This last-in, first-out behavior is the same principle used by a stack data structure. The largest number of simultaneously active frames is the Recursion depth. A depth proportional to $n$ commonly requires auxiliary stack space of $O(n)$.

3. Recurrences and efficiency

Measuring recursive cost

A Recurrence relates the cost of a problem of size $n$ to the cost of smaller problems. The recurrence must account for both recursive calls and the nonrecursive work performed in each call.

One call on a problem smaller by one

For factorial or a linear recursive scan,

There are approximately $n$ calls, so the running time is $O(n)$, and the call depth is also $O(n)$.

One call on half the input

Binary search reduces the problem to approximately half its former size:

The input can be halved only about $\log n$ times before reaching a constant-size problem. Therefore, the running time and recursive depth are both $O(\log n)$.

Multiple calls and repeated work

A naive recursive Fibonacci function has approximately the recurrence

It repeatedly solves the same subproblems, leading to exponential running time. Memoization stores each already-computed result, reducing the running time to $O(n)$ for this computation.

More generally, a divide-and-conquer algorithm with $a$ subproblems of size $n/b$ and additional work $f(n)$ has the form

A recursion tree, substitution, or the Master Theorem can help estimate such costs when applicable.

Takeaway: Count the recursive subproblems, the work done per call, and the maximum number of active calls separately.

4. Common recursive patterns

Linear and structural recursion

In linear recursion, each call makes one recursive call, often after processing one item. A search through an array can inspect the current item and then continue with the next index. This is frequently equivalent to a loop, although recursion can better express definitions over linked structures.

Structural recursion follows the shape of the data. For a linked list, the smaller subproblem is the list beginning at the next node. For a binary tree, the smaller subproblems are the left and right subtrees. A preorder traversal handles an empty tree as its base case, visits the current node, and then recursively processes both subtrees. A traversal of a tree with $n$ nodes takes $O(n)$ time when each node is visited once.

Tail recursion

In Tail recursion, the recursive call is the final operation. An accumulator can carry the result built so far, allowing the function to return the recursive call directly. Some languages replace the current frame during a tail call, but Python does not generally apply tail-call optimization. Consequently, tail-recursive Python code can still exhaust the recursion limit.

Divide and conquer

Divide and conquer divides a problem into smaller independent pieces, solves each piece recursively, and combines the results. Merge sort divides an array into two halves, recursively sorts both halves, and merges the sorted halves. Its recurrence is

which gives running time $O(n \log n)$.

Tree recursion and backtracking

Tree recursion makes multiple recursive calls, creating a branching call structure. Backtracking explores choices one at a time: apply a choice, recursively explore the resulting state, undo the choice, and try another choice. Backtracking is useful for permutations, maze solving, constraint satisfaction, and puzzle search. Its cost depends on the number of choices and on how effectively impossible partial solutions are pruned.

Takeaway: Choose a recursive pattern that matches the problem's structure, then analyze branching, combination work, and depth.

5. Choosing, proving, and reviewing

Recursion versus iteration

Many recursive algorithms can be rewritten with a loop and an explicit stack. Recursion is often clearer when the data is inherently recursive, when divide-and-conquer expresses the solution naturally, or when a search branches into choices. Iteration is often preferable when recursion only replaces a simple loop, inputs may be very large, stack space is limited, or the language has a low recursion limit.

An iterative replacement must store explicitly the information that recursive frames would have stored, such as pending nodes, indices, partial results, and return-state information. This can preserve the algorithm's behavior while making memory use more visible and avoiding runtime stack limits.

Proving correctness by induction

Induction mirrors the structure of a recursive algorithm:

1. Prove that the base case returns the correct result.

2. Assume recursive calls correctly solve smaller inputs.

3. Show that combining those correct smaller results produces the correct result for the current input.

For factorial, the base case $0! = 1$ is correct. If the call for $n-1$ correctly returns $(n-1)!$, then multiplying that result by $n$ produces

so the recursive step is correct.

A final review checklist

Before accepting a recursive algorithm, ask:

• Is every valid input covered by a reachable base case?

• Does every recursive call make progress toward a base case?

• Are recursive results combined correctly?

• Are any subproblems solved repeatedly, and would memoization help?

• What are the running time, auxiliary space, and maximum recursion depth?

• Would iteration be safer or clearer for the expected input size?

Final takeaway: A strong recursive algorithm combines a precise subproblem definition, complete stopping conditions, guaranteed progress, a correct combination step, and an explicit cost analysis.