05 Recursion

Foundations of Recursive Thinking

Recursion solves a problem by applying the same function to a smaller or simpler instance of that problem. A recursive algorithm is appropriate when the problem has a natural self-similar structure, such as a tree, a sorted search range, a linked list, or a set of choices.

A correct recursive design has two essential parts:

• The base case gives a direct answer and stops further calls.

• The recursive case makes progress toward the base case and uses the smaller result to solve the current problem.

For factorial, the mathematical definition is:

The recursive definition is:

The call on $n-1$ is smaller than the current problem, so repeated calls eventually reach $0$. The same design pattern appears in a sum function:

The key question is not simply whether a function calls itself. The key question is whether every possible execution path eventually reaches a valid stopping condition.

Tracing Calls with the Call Stack

Each active function call occupies a frame in the call stack. A frame stores information such as parameter values, local variables, the return location, and temporary computation state. When a function calls itself, a new frame is pushed. When the deeper call returns, its frame is removed and execution continues in the previous frame.

For a factorial call with input $4$, calls are created in this order:

• $factorial(4)$

• $factorial(3)$

• $factorial(2)$

• $factorial(1)$

• $factorial(0)$

After the base case returns, results are combined in reverse order:

• $factorial(0)=1$

• $factorial(1)=1\cdot 1=1$

• $factorial(2)=2\cdot 1=2$

• $factorial(3)=3\cdot 2=6$

• $factorial(4)=4\cdot 6=24$

This last-in, first-out behavior explains why recursion can use substantial memory even when each individual call uses little memory. For this factorial implementation, the maximum stack depth is $n+1$, so the call-stack space is $O(n)$. If calls continue indefinitely or become too deep, the program may encounter a stack overflow or a runtime recursion-limit error.

Takeaway: Trace both the downward sequence of calls and the upward sequence of returns. The maximum number of simultaneously active calls determines stack depth.

Designing and Verifying Recursive Algorithms

A systematic design process makes recursive algorithms easier to verify:

1. Define precisely what the function returns for an input of size $n$.

2. Identify the simplest valid input and use it to define the base case.

3. Reduce the input so that the recursive call receives a smaller problem.

4. Assume the smaller recursive call correctly solves its stated subproblem.

5. Use that result to construct the answer for the current input.

6. Verify that every path makes progress toward a base case.

7. Analyze both running time and space usage.

The recursive case commonly has three operations: reduce, call, and combine. In factorial, the reduction changes $n$ to $n-1$, the call computes $factorial(n-1)$, and the combination multiplies that result by $n$.

A base case must also have the correct value. Using $factorial(0)=0$ would stop the recursion but produce incorrect results, because the correct identity is $0!=1$. Similarly, a function such as bad(n) that calls itself with the unchanged argument has no meaningful progress, even if it contains a condition for $n=0$.

Takeaway: Correctness requires both termination and a correct relationship between the current result and the smaller result.

Common Recursive Patterns

Different recursive structures lead to different performance patterns.

• Decrease-and-conquer: One call handles a smaller problem, often of size $n-1$. For a sum of the first $n$ integers, there are $n+1$ calls, giving time $O(n)$ and stack space $O(n)$.

• Divide-and-conquer: A problem is divided into smaller parts. Binary search makes one call on approximately half the range, giving the recurrence $T(n)=T(n/2)+O(1)$ and running time $O(\log n)$.

• Recursive traversal: A tree function can process a node and then recursively process its children. With $n$ nodes, each node is processed once, so time is $O(n)$. Stack space is $O(h)$, where $h$ is the tree height.

• First-and-rest processing: A sequence function can inspect one element and recursively process the remaining elements. A worst-case linear search has time and stack space $O(n)$.

• Backtracking: The algorithm explores choices, records complete solutions, and reverses choices before trying alternatives. Its time can be exponential when the number of possible choices grows rapidly.

For two half-sized recursive calls with linear combination work, the recurrence is:

This is the pattern associated with merge sort and gives running time $O(n\log n)$.

Analyzing Time and Space

A recurrence relation makes the structure of recursive work explicit. The number of calls, the size of each subproblem, and the nonrecursive work at each call determine the final complexity.

For one call on a problem of size $n-1$:

For one call on a problem of size approximately $n/2$:

For two half-sized calls with linear work to combine results:

Branching call trees require attention to the branching factor, depth, work at each call, and repeated subproblems. Direct recursive Fibonacci illustrates the danger of repeated work:

The same smaller values are computed many times, producing commonly expressed exponential running time $O(2^n)$. Memoization stores each computed value, so values from $0$ through $n$ can be computed once. This reduces the time to $O(n)$ and uses $O(n)$ additional table space.

When analyzing space, distinguish call-stack space from auxiliary data space. A memoized algorithm can have both a recursion stack and a table of stored results.

Choosing Between Recursion and Iteration

Recursion and iteration can express the same computation with different resource usage. A factorial loop performs the multiplications from $2$ through $n$ without creating one call frame per input value. Both the straightforward recursive and iterative versions take time $O(n)$, but the recursive version uses $O(n)$ call-stack space while the iterative version can use $O(1)$ auxiliary space.

Recursion is often a good choice when:

• The data is recursively structured, especially a tree.

• The problem naturally divides into smaller subproblems.

• Recursive code expresses the solution more clearly than an explicit simulation.

• Backtracking is required.

Iteration may be preferable when:

• Input depth can be very large.

• Constant auxiliary space is important.

• The process is naturally sequential.

• The language has a restrictive recursion limit or does not optimize tail calls.

Before choosing recursion, check for missing base cases, unchanged arguments, incorrect base-case values, repeated subproblems, and excessive depth. A correct algorithm can still fail on large inputs if its call stack grows beyond the runtime limit. An iterative version, an explicit stack, or a more balanced divide-and-conquer strategy may address that limitation.

Final takeaway: Choose recursion for structure and clarity when its depth and memory costs are acceptable; choose iteration when predictable space usage or very large depth matters.