Recursion: base case and recursive case

A method that calls itself

• Recursion is when a method calls itself to solve a smaller piece of the same problem.
• On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
• Every recursive method needs two parts: a base case and a recursive case.

Base case and recursive case

• Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
• Recursive case: you call the same method with a smaller input, then build the answer.
• Without a base case, the method calls forever and crashes (a stack overflow).

Example: factorial

• factorial(n) means n * (n-1) * ... * 1. For example factorial(4) = 24.
• Base case: factorial(1) is 1.
• Recursive case: factorial(n) is n * factorial(n - 1).

public class Recursion {
    public static int factorial(int n) {
        if (n <= 1) {                  // base case
            return 1;
        }
        return n * factorial(n - 1);   // recursive case
    }
}

How the calls unwind

• Each call waits for the smaller call to finish. Then it multiplies and returns.
• Trace factorial(3). Calls go down, then answers come back up.

factorial(3) = 3 * factorial(2)        <- waits
  factorial(2) = 2 * factorial(1)      <- waits
    factorial(1) = 1                   <- base case, returns 1
  factorial(2) = 2 * 1 = 2             <- returns 2
factorial(3) = 3 * 2 = 6               <- returns 6

Example: sum to n

• sumTo(n) adds 1 + 2 + ... + n. For example sumTo(4) = 10.
• Base case: sumTo(0) is 0 (nothing to add).
• Recursive case: sumTo(n) is n + sumTo(n - 1).

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

Recursion over an array

• We can also recurse with an index that moves toward the end.
• Base case: when the index is past the last spot, return 0.
• Recursive case: add a[i] to the sum of the rest, arraySum(a, i + 1).

public class Recursion {
    public static int arraySum(int[] a, int i) {
        if (i >= a.length) {           // base case: past the end
            return 0;
        }
        return a[i] + arraySum(a, i + 1);
    }
}

• To sum the whole array you start at index 0: arraySum(a, 0).
• Each call handles one value and trusts the next call for the rest.

Common mistakes

• Recursion needs a base case, or it throws StackOverflowError.
• Each call must move closer to the base case.

Now you try

• Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
• A hidden Harness calls your method with several values and checks the result.
• Press Run to compile, then Check answer.