Recursion

🔁 Recursion

Part 1 of 7 — What Recursion Is

Topics in This Part

🔑 Key Concept: A recursive method is a method that calls itself to solve a smaller version of the same problem. Every recursive method needs two ingredients: a base case that stops the recursion, and a recursive case that moves toward the base case.

A Method That Calls Itself

Look at the classic example — factorial. By definition $n! = n \cdot (n-1)!$, and $0! = 1$. That mathematical definition translates almost word-for-word into Java:

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

The method factorial calls itself with a smaller argument (n - 1). It keeps shrinking the problem until it reaches n == 0, where it can answer directly without recursing.

⚠️ Every recursive method must have at least one base case. A recursive method with no reachable base case calls itself forever and crashes with a StackOverflowError.

Concept Check 🎯

Moving Toward the Base Case

A base case alone is not enough — the recursive call must make progress toward it. In factorial, each call uses n - 1, so n marches steadily down to 0.

factorial(4)
 → 4 * factorial(3)
        → 3 * factorial(2)
               → 2 * factorial(1)
                      → 1 * factorial(0)
                             → 1        (base case reached!)

Now the answers flow back up: $1 \to 1 \to 2 \to 6 \to 24$.

💡 The two-part test for a correct recursion:

1. Is there a base case that returns directly?
2. Does every recursive call get closer to that base case?

If a recursive call used n + 1 or unchanged, it would never reach — that is .

Spot the Bug 🐛

Trace It 🧮

Using the factorial method from this part:

1) What does factorial(3) return? 2) What does factorial(0) return?

🔁 Recursion

Part 2 of 7 — Tracing the Call Stack

🔑 The Idea: When a method calls itself, each call gets its own copy of the parameters and local variables, stacked on the call stack. Calls pause "on the way down" and resume "on the way up." Tracing this is the #1 recursion skill the AP exam tests.

How the Call Stack Works

Each method call is a stack frame. A new call is pushed on top; when it returns, it is popped off and control goes back to the caller, which resumes right where it paused.

Consider:

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

Tracing sum(3):

🔁 Recursion

Part 3 of 7 — Recursion vs. Iteration

🔑 The Idea: Anything you can do with a loop, you can do with recursion, and vice-versa. Recursion trades a loop variable for the call stack. Knowing how to convert between them — and the cost of each — is core AP CSA content.

The Same Job, Two Ways

Here is a sum from 1 to n, written iteratively and recursively:

// Iterative
public static int sumIter(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

// Recursive
public static int sumRec(int n) {
    if (n <= 0) return 0;
    return n + sumRec(n - 1);
}

🔁 Recursion

Part 4 of 7 — Recursion on Strings

🔑 The Idea: Strings are a favorite AP target for recursion. The trick is to peel off one character (usually the first or last) and recurse on the rest of the string using substring.

Peeling Off One Character

Two String methods power almost every recursive String problem:

Reverse a String by moving the first character to the end of the reversed rest:

public static String reverse(String s) {
    if (s.length() <= 1) return s;            // base case
    return reverse(s.substring(1)) + s.charAt(0);
}

Trace reverse("cat"):

reverse("cat") = reverse("at") + 'c'
reverse("at")  = reverse("t")  + 'a'
reverse("t")   = "t"                 (base case, length 1)

Unwinding: reverse("t") = "t" → reverse("at") = "t" + "a" = "ta" → .

🔁 Recursion

Part 5 of 7 — Fibonacci & Multiple Recursive Calls

🔑 The Idea: Some methods make two (or more) recursive calls. The most famous is Fibonacci, where each term is the sum of the two before it. Multiple calls cause the work to branch — which is powerful but can be expensive.

The Fibonacci Sequence

The Fibonacci numbers are $0, 1, 1, 2, 3, 5, 8, 13, \ldots$, defined by:

🔁 Recursion

Part 6 of 7 — Recursion on Arrays & Common Pitfalls

🔑 The Idea: To recurse over an array, pass an index that moves toward the end (or the length toward 0). Combined with the pitfalls section, this rounds out everything the AP exam asks about recursion.

Recursing Over an Array

Unlike a String, you can't easily "chop off" an array element, so you pass an index that advances toward arr.length. Here we sum an int[] starting at index i:

public static int arraySum(int[] arr, int i) {
    if (i == arr.length) return 0;             // base case: past the end
    return arr[i] + arraySum(arr, i + 1);      // add this element, recurse
}
// Called as arraySum(arr, 0) to sum the whole array.

Trace arraySum({4, 2, 7}, 0):

arraySum(arr,0) = 4 + arraySum(arr,1)
arraySum(arr,1) = 2 + arraySum(arr,2)
arraySum(arr,2) = 7 + arraySum(arr,3)
arraySum(arr,3) = 0          (i == length, base case)

Unwinding: $0 \to 7 \to 9 \to 13$. The array sums to .

🔁 Recursion

Part 7 of 7 — Mixed Practice & Mastery Check

You can now (1) identify base and recursive cases, (2) trace the call stack, (3) convert between recursion and iteration, (4) recurse on Strings and arrays, and (5) reason about Fibonacci-style branching. Let's put it together.

Quick Reference

⚠️ Top three mistakes: (1) no reachable base case → StackOverflowError; (2) forgetting to / use the recursive result; (3) wrong order of work relative to the call.