4.16 Recursion

4.16 Recursion

Recursion is a technique in which a method solves a problem by calling itself on a smaller version of that problem. The method must eventually stop calling itself; otherwise, the calls continue until the program runs out of stack space.

A useful everyday analogy is opening nested boxes: open the largest box, find a smaller box inside, open that one, and continue until the innermost box contains the answer. Then you work back outward, completing each waiting task in reverse order.

The two essential parts

Every correct recursive method has two logically distinct parts:

• A base case directly solves the smallest version of the problem.
• A recursive case calls the same method with an input that moves closer to the base case.

A recursive call is safe only when each call makes measurable progress toward a base case.

The Java runtime stores each active method call in a call stack, a last-in, first-out structure. When a method calls itself, the current call pauses while the new call runs; after the smaller call returns, the paused call resumes with the returned value.

Worked example: adding the integers from $1$ to $n$

Suppose sumTo(n) should compute $1 + 2 + \dots + n$. This method has the precondition $n \geq 1$:

public static int sumTo(int n) {
    if (n == 1) {
        return 1;                 // base case
    }
    return n + sumTo(n - 1);      // recursive case
}

The base case is n == 1, because the answer for $1$ is known immediately. The recursive case replaces the original problem with a smaller one: the sum through $n$ is $n$ plus the sum through $n - 1$.

For sumTo(4), the calls expand first and return afterward:

Stage	What happens
Expand	sumTo(4) waits for sumTo(3)
Expand	sumTo(3) waits for sumTo(2)
Expand	sumTo(2) waits for sumTo(1)
Base case	sumTo(1) returns $1$
Return	sumTo(2) returns $2 + 1 = 3$
Return	sumTo(3) returns $3 + 3 = 6$
Return	sumTo(4) returns $4 + 6 = 10$

The important detail is that n + sumTo(n - 1) cannot finish immediately: it must preserve the current value of n while waiting for the recursive call. The final result is therefore assembled during the return phase, not during the initial downward sequence of calls.

Tracing recursion precisely

To analyze a recursive method, trace it in two passes:

1. Follow calls downward. Record the argument passed to each recursive call.
2. Follow returns upward. Substitute each returned value into the waiting expression.

For sumTo(4), the argument sequence is $4, 3, 2, 1$. Because each argument decreases by $1$, and because the precondition guarantees the starting argument is at least $1$, the base case is eventually reached.

A second pattern: repeated self-calls

Some recursive methods make more than one recursive call. For example, a method that counts the ways to move through a staircase might split the problem into “take one step” and “take two steps.” Such methods create a branching call tree, so the number of calls can grow rapidly even when the input grows only a little.

This is why recursion should be judged not only by whether it produces the correct answer, but also by how many calls it creates and how much stack space it uses. A recursive solution can be elegant while still being inefficient.

Misconception check: recursion is not automatically infinite

Misconception — “A method that calls itself can never terminate.” Recursion terminates when every recursive path eventually reaches a base case. The real danger is a missing base case, a recursive call that never gets closer to it, or an input that violates the method’s precondition.

For example, sumTo(0) is not a valid call for the version above. It does not satisfy $n \geq 1$, so the method never reaches n == 1: it calls sumTo(-1), then sumTo(-2), and so on. A different contract could instead use if (n <= 0) return 0;, but the method’s behavior and documented input requirement must agree.

AP skills and reasoning processes

Topic 4.16 Recursion is associated with Skills 3, 4:

• Skill 3 — Analyze Code: trace recursive calls, identify the base case, determine returned values, and detect nonterminating recursion.
• Skill 4 — Document Code and Computing Systems: explain the method’s precondition, base case, recursive progress, and effect on the call stack.

A strong analysis does more than state the final number. It names the stopping condition, shows how the argument changes, and explains how the pending operations are completed as calls return.

Retrieval check

Consider sumTo(5). What argument sequence appears while calls are being made, what value does the base case return, and what final value is returned? Also state why sumTo(0) is invalid for the displayed implementation.