Recursive Reduction

Recursive reduction is the foundational recursion pattern. A method handles the case for input n by handling something small directly and delegating the rest to recursiveMethod(n - 1). Eventually n reaches a base case — usually 0 or 1 — where the method returns without recursing.

Every reduction-style recursion needs two parts: a base case that stops recursion, and a recursive case that makes progress toward the base case.

On the AP exam, this is the first recursion pattern tested. Mastering it is required before any other recursion topic makes sense.

The reduction template

public void recursiveMethod(int n) {
    if (n <= 0) return;            // base case
    // do something with n
    recursiveMethod(n - 1);        // shrink toward 0
}

Print countdown

public void countDown(int n) {
    if (n <= 0) return;
    System.out.println(n);
    countDown(n - 1);
}

Calling countDown(3) prints 3, 2, 1.

Sum from 1 to n

public int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n - 1);
}

Each call adds its value of n to the sum of everything smaller. sum(0) returns 0 — the base case prevents infinite recursion.

Power (positive exponent)

public int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

Each call peels off one factor of base; the exponent counts down to 0.

Why progress matters

Without n - 1 (or some step toward the base case), recursion never terminates — it crashes with a stack overflow. Every recursive call must move strictly closer to the base case.