Topic 4.16 Notes – Recursion

1. What Recursion Is

A recursive method is a method that calls itself.

It is just another form of repetition. Instead of a for or while loop changing a loop variable, recursion changes the parameter values in each call.

Every recursive method must have:

• Base case
  A condition where the method does not call itself. It returns a simple value and stops the chain.
• Recursive case
  The part where the method calls itself with a simpler input.

Here is the pattern you should instantly recognize:

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

When you see recursion, ask yourself:

• What makes it stop?
• How does each call get closer to stopping?

If nothing gets smaller or closer to the base case, the recursion never ends.

2. The Call Stack and Local Variables

Every method call creates a stack frame on the call stack.

That means each recursive call has:

• Its own copy of parameters
• Its own local variables
• Its own place waiting for a return value

Here’s what that looks like when we call example(3):

Call stack for example(3)

Notice how the calls build down until the base case, then the return values move back up in reverse order.

If we call example(3) using the method above, it expands like this:

example(3)
→ 3 + example(2)
→ 3 + (2 + example(1))
→ 3 + (2 + (1 + example(0)))
→ 3 + (2 + (1 + 0))
→ 6

Calls go downward until the base case.
Returns come back up in reverse order. This is Last In, First Out.

Important consequences:

• Changing n in one call does not affect other calls.
• If the base case is never reached, you get a StackOverflowError.

On multiple choice questions, they love testing whether you understand that each call has its own separate parameter value.

3. How to Trace Recursive Methods

Most questions ask something like: What is the result of calling this method?

Use this process:

1. Identify the base case.
2. Identify how the argument changes.
3. Write out the chain of calls.
4. Evaluate from the base case upward.

For methods that return a value, expand downward, then substitute upward.

For void methods:

• Code before the recursive call runs on the way down.
• Code after the recursive call runs on the way up.

That ordering detail shows up constantly in quizzes.

If there are multiple recursive calls in one method, trace each branch separately. Do not skip steps. Most mistakes come from jumping ahead mentally.

4. Common Recursive Patterns You Should Recognize

You are mainly expected to understand and trace these patterns.

a. Decreasing Counter Pattern

• Parameter decreases each time (n - 1)
• Base case usually n == 0 or n <= 1
• Often combines current value with recursive result

Used for sums, factorial-style logic, powers, etc.

b. Array or ArrayList with Index Parameter

Instead of shrinking the array, you move an index forward.

public static int sum(int[] arr, int index) {
    if (index >= arr.length) {
        return 0;
    }
    return arr[index] + sum(arr, index + 1);
}

• Base case: index >= arr.length
• Recursive case: move to index + 1

The index acts like a loop control variable.

c. String Processing with Index or Substring

Common structures:

• Base case: empty string or index at end
• Recursive call processes “the rest”
• Combine:
  • current character
  • recursive result

Example structure:

public static String reverse(String s) {
    if (s.length() == 0) {
        return "";
    }
    return reverse(s.substring(1)) + s.substring(0, 1);
}

Recognizing this structure quickly saves you time on both MCQs and FRQs.

5. Recursion vs Iteration and Common Mistakes

Recursion and Iteration Are Equivalent

Anything you can do with recursion can be done with a loop.

Connection:

• Loop variable ↔ recursive parameter
• Loop condition ↔ base case

Recursion is just repetition using method calls instead of loop syntax.

You are not required to write complex recursive code on the AP exam, but you must understand it.

Common Mistakes Tested

1. Missing base case
Infinite recursion → stack overflow.

2. No progress toward base case
Calling method(n) instead of method(n - 1).

3. Wrong base condition
Stops too early or too late, causing off-by-one errors.

4. Misunderstanding return timing
Values combine after recursive calls finish.

That last one is the most common tracing mistake.