The Two Parts of Every Recursive Method

public static int countdown(int n) {
    if (n == 0) {           // BASE CASE — stop here
        return 0;
    }
    return n + countdown(n - 1);  // RECURSIVE CASE — call with smaller n
}

Every recursive method has exactly two parts:

• Base case: the condition that stops the recursion and returns directly.
• Recursive case: calls the method again with a changed argument that moves toward the base case.

Tracing a Recursive Call

Tracing recursion requires two phases: the call phase (calls stack up) and the return phase (calls unwind, returning values).

countdown(3) → needs 3 + countdown(2)
  countdown(2) → needs 2 + countdown(1)
    countdown(1) → needs 1 + countdown(0)
      countdown(0) → BASE CASE: returns 0

      countdown(0) = 0
    countdown(1) = 1 + 0 = 1
  countdown(2) = 2 + 1 = 3
countdown(3) = 3 + 3 = 6

Common Recursive Patterns

Factorial

public static int factorial(int n) {
    if (n == 0) return 1;           // base case
    return n * factorial(n - 1);   // recursive case
}
// factorial(4) = 4 * 3 * 2 * 1 * 1 = 24

Sum of Digits

public static int sumDigits(int n) {
    if (n < 10) return n;                        // base case: single digit
    return n % 10 + sumDigits(n / 10);           // recursive case
}
// sumDigits(123) = 3 + sumDigits(12)
//                = 3 + 2 + sumDigits(1)
//                = 3 + 2 + 1 = 6

String Recursion

public static String reverse(String s) {
    if (s.length() == 0) return "";                           // base case
    return reverse(s.substring(1)) + s.charAt(0);            // recursive case
}
// reverse("abc") = reverse("bc") + 'a'
//                = reverse("c") + 'b' + 'a'
//                = reverse("") + 'c' + 'b' + 'a'
//                = "" + "c" + "b" + "a" = "cba"

Tracing Strategy for the AP Exam

When a recursive trace question appears on the AP exam:

1. Write out each call as an indented line.
2. Find the base case — that's where the unwinding starts.
3. Work back up the chain, substituting return values.
4. The outermost call's return value is your answer.

Summary

• Every recursive method has a base case (stops) and a recursive case (calls itself with a smaller input).
• Trace by stacking calls down to the base case, then unwinding back up.
• Missing base case = infinite recursion = StackOverflowError.
• The AP exam tests tracing, not writing recursive methods from scratch.

public static int mystery(int n) {
    if (n == 0) return 0;
    return n + mystery(n - 1);
}

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

public static void count(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    count(n - 1);
}
count(4);

public static void countUp(int n) {
    if (n == 0) return;
    countUp(n - 1);
    System.out.print(n + " ");
}
countUp(4);

public static int mystery(int n) {
    if (n < 10) return n;
    return n % 10 + mystery(n / 10);
}

public static int sumDown(int n) {
    if (n == 0) return 1;
    return n + sumDown(n - 1);
}

public static int f(int n) {
    if (n <= 1) return 1;
    return f(n - 1) + f(n - 2);
}

public static int mystery(int n) {
    if (n == 0) return 0;
    return n + mystery(n - 1);
}