4.16 Recursion

What you need to know

• A recursive method calls itself. It needs a base case (a condition where it returns without recursing) and a recursive call that moves toward the base case.
• Without a reachable base case, recursion never ends — a run-time stack overflow.
• Each call has its own copies of parameters and local variables. Changes in one call don't affect the others.
• Tracing: write each call with its argument, stop at the base case, then substitute return values back up the chain. Or draw the calls as a stack.
• Number of calls is a common question: count every invocation including the original.
• Any recursive method can be rewritten with a loop, and vice versa; recursion often mirrors the structure of the problem (factorial, sum of a list, string reversal).
• The revised CED says you will trace recursive code, not write it — FRQs won't require recursion.

Worked example

public static int f(int n)
{
    if (n <= 1) return 1;          // base case
    return n * f(n - 1);           // recursive call
}
// f(4) = 4 * f(3)
//      = 4 * (3 * f(2))
//      = 4 * (3 * (2 * f(1)))
//      = 4 * (3 * (2 * 1)) = 24
// Calls made: f(4), f(3), f(2), f(1) → 4 calls

public static void printDown(int n)
{
    if (n == 0) return;
    System.out.print(n + " ");
    printDown(n - 1);
}
// printDown(3) prints: 3 2 1

Trace it yourself

Step through with the buttons, or use the ← → keys. Changed variables are highlighted.

Going deeper

The nuance, edge cases, and connections that turn a 3 into a 5.

• Structure: base case(s) first (return without recursing), then recursive case(s) (call with a smaller/closer argument, combine the result). If the argument doesn't get closer to a base case, infinite recursion → StackOverflowError.
• Each call has its own frame: its own parameters and locals. When f(4) calls f(3), f(4)'s n is still 4; f(3)'s n is 3. Changes in the inner call don't affect the outer.
• Two tracing techniques. Substitution: expand f(4) = 4 * f(3) = 4 * 3 * f(2) … until base, then multiply back. Stack: list the calls in a column as they happen; when the base returns, cross off from the bottom up, writing each return value.
• Order of side effects: a print before the recursive call happens on the way down (n, n−1, …). A print after happens on the way up (…, n−1, n). Same code, reversed output.
• Counting calls: include the original. f(n) with f(n−1) makes n calls to reach f(1)… or n+1 to reach f(0). Halving (f(n/2)) makes about log₂ n + 1 calls.
• Base case correctness: the recursion must hit it exactly. if (n == 0) with f(n - 2) from an odd n skips 0 and never stops. if (n <= 0) is the safe form.
• Recursion on Strings and arrays: process the first character, recurse on the rest (s.substring(1)); or use an index parameter that increments. Base case: empty string / index == length.
• Any loop can be recursion and vice versa. The exam may show a recursive method and ask which loop is equivalent.
• The 2025–26 CED says recursion is traced, not written. FRQs won't require it. Multiple choice will trace it.

Mistakes that cost points

• Not tracking each frame's own variables. Inner calls don't change outer variables.
• Printing in the wrong order. Before the call = descending. After = ascending.
• Miscounting calls. Include the first call and the base-case call.
• Missing a skipped base case. Check whether the argument sequence actually hits it.

Practice questions

Written in the style of the real exam. Try each one before revealing the answer.

public static int g(int n)
{
    if (n == 0) return 0;
    return n + g(n - 2);
}

public static void p(int n)
{
    if (n > 0)
    {
        p(n - 1);
        System.out.print(n + " ");
    }
}

public static int h(int n)
{
    if (n < 1) return 0;
    return 1 + h(n / 2);
}