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 n unchanged, it would never reach n == 0 — that is infinite recursion.

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):

💡 The recursive calls stack up until the base case, then the partial results unwind back up. sum(3) returns 6 — which makes sense, since $3 + 2 + 1 = 6$.

Trace the Stack 🧮

Using sum above (if (n <= 0) return 0; return n + sum(n - 1);):

1) What does sum(4) return? 2) How many total calls to sum occur when evaluating sum(4) (count sum(4) itself)?

Code Before vs. After the Recursive Call

Statements before the recursive call run on the way down; statements after it run on the way up. This is why the order of output can surprise you.

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

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

⚠️ Same numbers, reversed order. In mystery2, every print waits until the deeper call finishes, so the smallest n prints first. Watching where the work happens relative to the recursive call is essential.

Output Order 🎯

Fill the Trace 🔽

Trace sum(2) for int sum(int n){ if(n<=0) return 0; return n + sum(n-1); }.

🔁 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 shines when a problem is naturally defined in terms of smaller copies of itself — trees, nested structures, "divide and conquer." For simple counting, a loop is usually simpler and uses less memory.

Concept Check 🎯

Worked Conversion: Power

Compute $b^e$ (b to the power e) for a non-negative integer exponent. The recursive definition is $b^e = b \cdot b^{\,e-1}$ with $b^0 = 1$.

public static int power(int b, int e) {
    if (e == 0) return 1;            // base case: b^0 = 1
    return b * power(b, e - 1);      // recursive case
}

Trace power(2, 3):

$2 \cdot \text{power}(2,2) = 2 \cdot 2 \cdot \text{power}(2,1) = 2 \cdot 2 \cdot 2 \cdot \text{power}(2,0) = 2 \cdot 2 \cdot 2 \cdot 1 = 8$

✅ Check: $2^3 = 8$ ✓. The exponent (not the base) shrinks toward the base case e == 0.

Trace Power 🧮

Using power(int b, int e) above (if (e == 0) return 1; return b * power(b, e - 1);):

1) What does power(3, 2) return? 2) What does power(5, 0) return? 3) What does power(2, 4) return?

Match Loop to Recursion 🔽

You're converting the loop for(int i=1;i<=n;i++) total+=i; into a recursive sumRec(int n). Choose each correct piece.

🔁 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" → reverse("cat") = "ta" + "c" = "tac".

💡 The base case s.length() <= 1 handles both a single character and the empty string "" — a one-character string reversed is itself.

Trace the String 🎯

Counting With Recursion

To count something in a String, add 1 (or 0) for the first character, then recurse on the rest. Here we count occurrences of a target character:

public static int countChar(String s, char c) {
    if (s.length() == 0) return 0;           // base case: empty
    int rest = countChar(s.substring(1), c); // count in the rest
    if (s.charAt(0) == c) {
        return 1 + rest;
    }
    return rest;
}

Trace countChar("banana", 'a'):

b → 0 + count("anana")
a → 1 + count("nana")
n → 0 + count("ana")
a → 1 + count("na")
n → 0 + count("a")
a → 1 + count("")  → 1 + 0

Adding the 1s: there are 3 a's in "banana".

⚠️ Notice the recursion always shrinks the string with substring(1), and the base case is the empty string "". The if only decides whether to add 1 — it does not stop the recursion.

Count It 🧮

Using countChar(String s, char c) above:

1) countChar("mississippi", 's') returns? 2) countChar("hello", 'z') returns? 3) countChar("aaaa", 'a') returns?

Build the Reverse 🔽

Complete the recursive reverse trace for reverse("hi").

🔁 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:

$F(0) = 0, \quad F(1) = 1, \quad F(n) = F(n-1) + F(n-2)$

In Java, this needs two base cases and two recursive calls:

public static int fib(int n) {
    if (n == 0) return 0;            // base case
    if (n == 1) return 1;            // base case
    return fib(n - 1) + fib(n - 2);  // TWO recursive calls
}

💡 Each value is the sum of the two before it: $F(5) = F(4) + F(3) = 3 + 2 = 5$. Always confirm both base cases first — fib would never terminate with only n == 0, because fib(1) would try to compute fib(0) + fib(-1).

Compute Fibonacci 🧮

Using fib above:

1) fib(4) returns? 2) fib(6) returns? 3) fib(2) returns?

The Cost of Branching

Because fib calls itself twice, the calls form a tree, and the same subproblems are recomputed many times. Here is the call tree for fib(4):

            fib(4)
          /        \
      fib(3)        fib(2)
      /    \        /    \
  fib(2)  fib(1) fib(1) fib(0)
  /    \
fib(1) fib(0)

Count the calls: fib(4) triggers 9 total calls to fib (1 + 2 + 2 + 2 + 2... count the nodes: fib(4), two children, etc. — there are 9 nodes). Notice fib(2) is computed twice and fib(1) three times — wasted work.

⚠️ This naïve Fibonacci is exponentially slow ($O(2^n)$-ish). It is correct and great for learning recursion, but in practice you'd use iteration or "memoization" to avoid recomputing. On the AP exam, you mainly need to trace it and count calls.

Reason About the Tree 🎯

Build Fibonacci 🔽

Complete the recursive fib and read the sequence.

🔁 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 {4, 2, 7} sums to 13.

💡 The index i is the "loop variable" of the recursion. The base case fires when i reaches arr.length — there is no element at that index, so we return the identity value 0.

Trace the Array 🧮

Using arraySum(int[] arr, int i) above, with arr = {5, 1, 3, 6}:

1) arraySum(arr, 0) returns? 2) arraySum(arr, 2) returns? (starts at index 2) 3) arraySum(arr, 4) returns? (index equals length)

Common Pitfalls (Memorize These)

⚠️ Most common AP free-response error: writing fib(n-1) + fib(n-2) but forgetting the return, or recursing without using the returned value. A recursive call's result is useless unless you return it (or store/combine it).

Diagnose the Bug 🐛

Fix the Recursion 🔽

You want countdown(n) to print n, n-1, ..., 1 then stop. Choose each correct piece.

🔁 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 return / use the recursive result; (3) wrong order of work relative to the call.

Mixed Practice 🎯

One More Trace 🧮

int h(int n){ if(n<=1) return 1; return n * h(n-1); }

1) h(4) returns? (this is factorial) 2) For int p(int n){ if(n==0) return 0; return n + p(n-2); }, what does p(6) return? (adds n, n-2, n-4, ...)

Exit Quiz ✅

Answer all three to finish the lesson.