Recursion Explained Simply for AP CS A

Recursion is the topic that confuses AP CS A students more than any other. It feels circular: a method that calls itself? How does that ever stop? How do you even follow what's happening?

The good news: recursion follows a simple, consistent pattern. Once you understand that pattern and practice tracing a few examples by hand, it stops feeling mysterious. This guide builds up from first principles, traces several examples step by step, and covers everything the AP CS A exam actually tests on recursion.

What Recursion Is

A recursive method is a method that calls itself as part of solving a problem. Instead of solving the whole problem at once, a recursive method solves a small piece and then hands the rest off to another call of the same method.

Here's the key insight: each time the method calls itself, it does so with a smaller or simpler version of the problem. Eventually the problem becomes so simple that it can be answered directly, without another call. That's when the chain stops.

Every correct recursive method has exactly two parts:

• The base case: the simplest possible input, handled directly without another recursive call. This is what stops the recursion.
• The recursive case: everything else. The method calls itself with a smaller input, then uses that result to produce the answer for the current input.

If you write a recursive method without a base case, the method calls itself forever (or until Java runs out of memory and throws a StackOverflowError). The base case is not optional.

The First Example: Factorial

Factorial is the classic introduction to recursion. The factorial of a positive integer n (written n!) is the product of all integers from 1 to n.

5! = 5 × 4 × 3 × 2 × 1 = 120

Notice the pattern: 5! = 5 × 4!. And 4! = 4 × 3!. And so on, until 1! = 1, which we just know. That's the structure of a recursive solution: express the answer in terms of a smaller version of the same problem.

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

When you call factorial(5), here's what happens:

• factorial(5) returns 5 * factorial(4)
• factorial(4) returns 4 * factorial(3)
• factorial(3) returns 3 * factorial(2)
• factorial(2) returns 2 * factorial(1)
• factorial(1) returns 1  ← base case, no more calls

Now the chain unwinds:

• factorial(2) gets 1 back, returns 2 * 1 = 2
• factorial(3) gets 2 back, returns 3 * 2 = 6
• factorial(4) gets 6 back, returns 4 * 6 = 24
• factorial(5) gets 24 back, returns 5 * 24 = 120

The final answer is 120, which is correct.

How to Trace Recursion: The Call Stack

When the exam asks you to trace a recursive method, draw the call stack. This is a list of method calls, one per line, showing what each call is waiting for. New calls go on top; completed calls get crossed off and their return value passes down.

Here's the call stack for factorial(4) drawn out:

factorial(4)  waiting for factorial(3)...
  factorial(3)  waiting for factorial(2)...
    factorial(2)  waiting for factorial(1)...
      factorial(1)  returns 1  ✓ base case

    factorial(2)  gets 1, returns 2 * 1 = 2
  factorial(3)  gets 2, returns 3 * 2 = 6
factorial(4)  gets 6, returns 4 * 6 = 24

This is the single most useful technique for recursion problems on the exam. Don't try to trace in your head; write it down.

The "Trust the Recursion" Mindset

One of the hardest mental shifts with recursion is learning to trust it. When you write the recursive case, you call the method on a smaller input and use the result. You don't need to trace through that entire smaller call in your head; just assume it returns the correct answer for that smaller input.

For example, when writing factorial(n), trust that factorial(n - 1) correctly returns (n-1)!. Your only job is to multiply by n to get n!. That's it.

This mindset is called the "recursive leap of faith." It's how experienced programmers think about recursion, and it's what lets you write recursive methods quickly and correctly without getting lost in nested calls.

More Examples

Sum of digits

Given a non-negative integer, return the sum of its digits. For example, sumDigits(253) should return 10 (2 + 5 + 3).

The pattern: the last digit of any number n is n % 10. The remaining digits form the number n / 10 (integer division). So summing the digits of n is the same as the last digit plus the sum of the digits of n / 10.

public static int sumDigits(int n) {
    if (n < 10) {       // base case: single digit
        return n;
    }
    return (n % 10) + sumDigits(n / 10); // recursive case
}

Trace for sumDigits(253):

sumDigits(253)  → 3 + sumDigits(25)
  sumDigits(25)   → 5 + sumDigits(2)
    sumDigits(2)    → 2  ✓ base case (2 < 10)
  sumDigits(25)   → 5 + 2 = 7
sumDigits(253)  → 3 + 7 = 10

Count occurrences in a String

Count how many times a character appears in a String. For example, countChar("banana", 'a') should return 3.

The pattern: look at the first character. If it matches, add 1 and recurse on the rest of the String. If it doesn't match, add 0 and recurse on the rest. The base case is an empty String, which contains 0 of any character.

public static int countChar(String s, char c) {
    if (s.length() == 0) {   // base case: empty string
        return 0;
    }
    int first = (s.charAt(0) == c) ? 1 : 0;
    return first + countChar(s.substring(1), c); // recursive case
}

Trace for countChar("ana", 'a'):

countChar("ana", 'a')  → 1 + countChar("na", 'a')
  countChar("na", 'a')   → 0 + countChar("a", 'a')
    countChar("a", 'a')    → 1 + countChar("", 'a')
      countChar("", 'a')     → 0  ✓ base case
    countChar("a", 'a')    → 1 + 0 = 1
  countChar("na", 'a')   → 0 + 1 = 1
countChar("ana", 'a')  → 1 + 1 = 2

Reverse a String

The pattern: the reverse of a String is the last character, followed by the reverse of everything except the last character. The base case is a String of length 0 or 1, which is already its own reverse.

public static String reverse(String s) {
    if (s.length() <= 1) {   // base case
        return s;
    }
    // last character + reverse of everything before it
    return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
}

Trace for reverse("cat"):

reverse("cat")  → 't' + reverse("ca")
  reverse("ca")   → 'a' + reverse("c")
    reverse("c")    → "c"  ✓ base case
  reverse("ca")   → 'a' + "c" = "ac"
reverse("cat")  → 't' + "ac" = "tac"

Recursive search in an array

Check whether a value exists in an array, looking at one element per call.

public static boolean contains(int[] arr, int target, int index) {
    if (index == arr.length) {    // base case: ran off the end
        return false;
    }
    if (arr[index] == target) {   // base case: found it
        return true;
    }
    return contains(arr, target, index + 1); // recursive case
}

You'd call this as contains(arr, target, 0) to start at the beginning. The index parameter tracks where you are; it increases by 1 with each call until you find the target or exhaust the array.

What the AP CS A Exam Actually Tests

The exam tests recursion in two ways: reading/tracing recursive code, and occasionally writing a simple recursive method.

Tracing questions (most common)

You'll be shown a recursive method and asked: what does mystery(5) return? Or: how many times is the method called? These are solved by drawing the call stack and working through it step by step.

Common exam patterns include "mystery" methods that are disguised versions of familiar algorithms. Before tracing, ask: is this computing a sum? A count? Building up a String? Identifying the purpose first helps you trace more quickly and catch errors.

What to look for when tracing

• Identify the base case first. What input causes the method to return without another recursive call? That's where the chain stops.
• Identify what changes between calls. Usually one parameter shrinks (n - 1, s.substring(1), index + 1). Confirm the change is moving toward the base case, not away from it.
• Trace one call at a time. Write down the argument, identify which branch executes (base or recursive), note the return value, then move up the stack.

Writing questions (less common but do appear)

You may be asked to complete a recursive method or write one from scratch. The approach:

1. Identify the base case: what's the simplest input, and what should be returned for it?
2. Write the recursive case: assume the method works correctly for a smaller input, then use that result to build the answer for the current input.
3. Verify: trace your method with a small example by hand to confirm it produces the right answer.

Recursion vs. Iteration

Any problem solvable with recursion can also be solved with a loop, and vice versa. The exam won't ask you to defend your choice, but understanding the relationship helps you recognize what a recursive method is doing.

Here's the same problem solved both ways, so you can see the parallel structure:

// Recursive: sum integers from 1 to n
public static int sumTo(int n) {
    if (n == 1) return 1;
    return n + sumTo(n - 1);
}

// Iterative: sum integers from 1 to n
public static int sumTo(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

Both return the same result. The recursive version is more concise; the iterative version is often easier to trace at a glance.

Common Mistakes on the Exam

1. Missing or wrong base case. If the base case condition is never reached, you get infinite recursion. Check: does the recursive call always move the argument closer to the base case? For factorial(n), each call decreases n by 1 toward the base case of n == 1. If you wrote n == 0 as the base case but the call is factorial(n - 1) starting from a positive integer, you'd reach 0 and then go negative forever.
2. Forgetting that each call has its own local variables. Variables declared inside a recursive method are not shared between calls. Each call gets its own fresh copy of every local variable. This is a feature, not a bug: it's what lets each level of the call stack keep track of its own state independently.
3. Returning before the recursive call when you shouldn't. A common mistake on tracing questions is assuming the method returns as soon as it hits a return statement somewhere in the middle of the call stack. The return value from the recursive call still has to propagate back up through each waiting call.
4. Confusing the number of calls with the return value. Exam questions sometimes ask "how many times is the method called?" rather than "what does it return?" These are different questions. For factorial(5), the method is called 5 times (with arguments 5, 4, 3, 2, 1) and returns 120. Don't mix them up.
5. Not accounting for the initial call when counting calls. The call factorial(5) itself counts. The total number of calls for factorial(n) is n, not n - 1.

A Tracing Template

For any recursion tracing question on the exam, use this process:

1. Write the initial call at the top of your scratch paper with its argument.
2. Apply the method: which branch runs? If it's the base case, write the return value and stop. If it's the recursive case, write what the method returns in terms of the next call, then write that next call below it.
3. Keep expanding until you hit the base case.
4. Work back up: substitute each return value into the expression above it.
5. The return value of the first call is your answer.

Here's the template applied to a mystery method:

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

Trace mystery(6):

mystery(6)  → 6 + mystery(4)
  mystery(4)  → 4 + mystery(2)
    mystery(2)  → 2 + mystery(0)
      mystery(0)  → 0  ✓ base case (0 <= 0)
    mystery(2)  → 2 + 0 = 2
  mystery(4)  → 4 + 2 = 6
mystery(6)  → 6 + 6 = 12

What does this method compute? It sums all even positive integers from 2 up to n (when n is even). Recognizing the purpose after tracing helps you verify the answer is plausible.

Ready to Practice?

Recursion gets easier every time you trace a new example by hand. The pattern is always the same: find the base case, find what changes each call, draw the stack going down, unwind coming back up. After a dozen examples it becomes second nature.

ExamReadyUSA's 4-week AP CS A Crash Course includes a dedicated recursion session with guided tracing practice and FRQ problems graded by Namrata Poladia, a College Board AP Reader who scores real AP exams. Groups are capped at 5 students so every question gets a thorough answer.