Recursion in Java: Tracing and Algorithms

The Structure of Recursion

Recursion solves a problem by repeatedly reducing it to a smaller problem with the same structure. A correct recursive method has two essential parts: a base case and a recursive case.

The base case gives a result without making another call. The recursive case makes a recursive call and must change the problem so that the base case will eventually be reached. For a countdown, the arguments might be $3$, $2$, $1$, and finally $0$. At $0$, the method stops instead of calling itself again.

For a factorial computation, the reduction can be written as

with the stopping rule $0! = 1$. Thus, the computation for $4!$ becomes $4 \cdot 3 \cdot 2 \cdot 1 \cdot 1 = 24$.

Two checks are essential:

• The method must have a reachable base case.

• Every recursive call must move closer to that base case.

A method with no base case never stops. A method whose argument moves away from its base case also fails to terminate and may eventually cause a StackOverflowError.

Takeaway: Identify the smallest valid problem first, then verify that every recursive call makes that problem smaller or simpler.

Tracing Calls and Returns

Every method invocation creates a separate stack frame on the call stack. When a recursive method calls itself, the current invocation pauses while the new invocation runs. This creates a downward sequence of calls followed by an upward sequence of returns.

Consider a method that returns the sum from $1$ through $n$. A call with $n = 4$ creates the sequence

The base call returns $1$. The suspended calls then resume:

• $\text{sumTo}(2)$ returns $2 + 1 = 3$.

• $\text{sumTo}(3)$ returns $3 + 3 = 6$.

• $\text{sumTo}(4)$ returns $4 + 6 = 10$.

Each invocation has its own parameter value. The $n$ in the call with argument $4$ is distinct from the $n$ in the call with argument $3$.

When tracing a method, write the calls downward until a base case is reached, then evaluate the suspended calls upward. Keep printed output separate from returned values. A statement before the recursive call executes while the calls are being made; a statement after the recursive call executes while the calls are returning. Therefore, printing before the call can produce $3$, $2$, $1$, while printing after the call can produce $1$, $2$, $3$.

Takeaway: Trace in two phases: follow calls toward the base case, then resolve returns in reverse order.

Recursive Processing of Strings and Arrays

Recursive methods can process one part of a string or array at a time and combine the result with the rest.

For a string, a common strategy is to inspect the first character and recursively process the remaining substring. For example, counting the character 'a' in "banana" examines each character in turn and reaches the empty string. The empty string is the natural base case because it contributes a count of $0$.

A string reversal can remove the first character, reverse the remainder, and append the removed character at the end. The computation for "cat" follows this pattern:

A palindrome test compares the first and last characters. If they match, the method recursively checks the substring between them. A string of length at most $1$ is a palindrome, and a mismatch immediately produces false.

For an array, an index parameter identifies the portion that remains. An array-sum method can add the element at index $i$ to the sum beginning at index $i+1$. When $i$ reaches the array length, no elements remain and the contribution is $0$. For the values $4$, $7$, and $2$, the result is $4 + 7 + 2 = 13$.

The same pattern supports counting elements that satisfy a condition or finding a maximum. A maximum method must define what happens for an empty array before attempting to access an element.

Takeaway: For strings, shrink the substring; for arrays, advance an index or narrow a range. In both cases, define the empty or smallest input explicitly.

Divide-and-Conquer Algorithms

Recursion is especially useful when a problem repeatedly divides into smaller regions.

Binary search requires a sorted array. It examines the middle index, compares that value with the target, and recursively searches only the half that could still contain the target. For the sorted values 3, 8, 12, 17, 25, 31, 40 and target 25, the middle values are 17, then 31, then 25. The target is found at index $4$. If the lower bound becomes greater than the upper bound, the range is empty and the search returns $-1$.

Merge sort uses a different divide-and-conquer pattern:

1. Divide the collection into left and right portions.

2. Recursively sort both portions.

3. Merge the two sorted portions.

A portion containing zero or one element is already sorted. For the values 8, 3, 6, 2, the method sorts 8, 3 into 3, 8, sorts 6, 2 into 2, 6, and then merges them into 2, 3, 6, 8.

Binary search eliminates half of a search range at each step, whereas merge sort creates two recursive branches and later combines their results. When tracing either algorithm, record the current bounds or subranges carefully and check the boundary conditions.

Takeaway: Binary search narrows one sorted range; merge sort recursively sorts two halves and combines them.

Designing and Evaluating Recursive Solutions

A reliable way to design or analyze a recursive method is to answer five questions:

1. What is the smallest valid problem?

2. What condition identifies that problem?

3. What smaller problem does the recursive call solve?

4. How are the current result and recursive result combined?

5. What initial input and boundary conditions are required?

For an array-sum method, the smallest problem is that no elements remain. The base condition is that the index equals the array length. The smaller problem begins at the next index, the progress measure is an index increase of $1$, and the combination is the current value plus the recursive sum.

Boundary conditions vary by algorithm:

• An empty string may be the base case for character processing.

• An array maximum method may require a nonempty array.

• A search range is empty when the lower bound exceeds the upper bound.

• A merge-sort portion is finished when it has zero or one element.

Recursion and iteration can express the same repetition. An iterative sum updates an accumulator inside a loop, while a recursive sum combines $n$ with the sum for $n-1$. Iteration generally uses less call-stack memory for simple repetition, while recursion can express divide-and-conquer or nested structures clearly.

When answering a tracing question, distinguish three different things: the arguments at each invocation, the order of printed output, and the value returned by each invocation. A branching method such as a recurrence with calls on $n-1$ and $n-2$ creates a call tree rather than a single chain.

Final checklist: Find the base case, verify progress, trace calls downward, resolve results upward, and inspect empty-input and boundary cases.