4.16 Recursion

What is recursion in AP Computer Science A?

Recursion is when a method calls itself to solve a problem by breaking it into smaller versions of the same problem. Every recursive method needs at least one base case that stops the recursion and at least one recursive call that moves toward that base case. On the AP Computer Science A exam, recursion shows up only in multiple-choice, where your job is to trace calls and figure out the result or describe what the method does.

more resources to help you study

practice multiple choiceFRQ practice & scoringcheatsheetsscore calculator

Why This Matters for the AP Computer Science A Exam

Recursion is assessed only through the multiple-choice section of the AP Computer Science A exam. You will not be asked to write recursive code, so the skill you actually need is reading a recursive method and predicting its output or behavior.

Questions usually ask you to do one of two things:

• Determine the result of a specific call to a recursive method.
• Describe the overall behavior or purpose of a recursive method.

A call to a recursive method works exactly like a call to a normal method. Plugging in a specific input value and tracing the calls shows how the method behaves for that input. After tracing a few inputs, you can generalize what the method does overall. Because recursion is another form of repetition, the same tracing habits you built with loops carry over here.

Key Takeaways

• A recursive method calls itself and must contain at least one base case and at least one recursive call.
• The base case halts the recursion. Without one, the calls never stop.
• Each recursive call gets its own set of local variables and parameters, so values are tracked separately at each level.
• Parameter values track progress through the recursion, similar to how a loop control variable tracks progress through a loop.
• Any recursive solution can also be written iteratively, and any iterative solution can be written recursively.
• For the exam, focus on tracing calls and describing behavior, not on writing recursive code.

How Recursion Works

Every recursive method has two essential parts:

• A base case that stops the recursion and returns a result directly.
• A recursive case that calls the method again with a simpler or smaller input that moves toward the base case.

The pattern is always the same: check the base case first, then make the recursive call on a smaller version of the problem. Here is a factorial example you can trace.

</>Java
// Factorial: n! = n * (n-1) * (n-2) * ... * 1
// 5! = 5 * 4 * 3 * 2 * 1 = 120
public static int factorial(int n) {
    // Base case: simplest version of the problem
    if (n <= 1) {
        return 1;  // 0! = 1 and 1! = 1
    }

    // Recursive case: solve smaller problem and combine result
    return n * factorial(n - 1);

}

When you call factorial(4), the method does not finish right away. It pauses to call factorial(3), which pauses to call factorial(2), and so on until factorial(1) hits the base case and returns 1. Then the results combine on the way back up:

</>Code
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1            (base case)

factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Each Call Has Its Own Variables

This is the idea that trips up the most students. Each recursive call has its own copy of the parameters and local variables. When factorial(4) calls factorial(3), the value n = 4 does not disappear. It waits until the inner call returns, then finishes its own line.

Those paused calls stack up. The most recent call runs to completion first, then the one before it, then the one before that. That is why results combine in reverse order, from the base case back up to the original call.

Tracing Recursion

Most recursion questions on the AP Computer Science A exam are tracing problems. A reliable method:

• Write down the first call with its actual argument values.
• Each time the method reaches a recursive call, pause the current call and write the new call underneath it.
• Keep going until a call reaches the base case and returns a value directly.
• Substitute that returned value back into the call that was waiting for it, and work your way back up.

Here is the same approach applied to a sum method:

</>Java
public static int sumToN(int n) {
    // Base case
    if (n <= 0) {
        return 0;
    }

    // Recursive case: n + sum of numbers from 1 to n-1
    return n + sumToN(n - 1);

}

Tracing sumToN(3):

</>Code
sumToN(3) = 3 + sumToN(2)
sumToN(2) = 2 + sumToN(1)
sumToN(1) = 1 + sumToN(0)
sumToN(0) = 0              (base case)

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

Methods With More Than One Recursive Call

Some methods make more than one recursive call in a single line, like a Fibonacci method.

</>Java
public static int fibonacci(int n) {
    // Base cases
    if (n <= 1) {
        return n;
    }

    // Recursive case: F(n) = F(n-1) + F(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);

}

When a method calls itself twice, fully evaluate the left call before the right call. It helps to draw a small tree, where each call branches into the calls it makes, and fill in the returned values from the bottom up.

Recursion With Strings, Arrays, and Lists

Recursion can also walk through a String, an array, or an ArrayList. The common pattern is to handle one element and let the recursive call handle the rest, usually by passing an index that moves toward the end.

</>Java
// Count occurrences of a target value in an array
public static int countOccurrences(int[] arr, int target, int index) {
    // Base case: reached end
    if (index >= arr.length) {
        return 0;
    }

    // Recursive case: add 1 if match, plus count in rest
    int currentCount = (arr[index] == target) ? 1 : 0;
    return currentCount + countOccurrences(arr, target, index + 1);
}

A String example works the same way, processing one character at a time:

</>Java
// Count how many times a character appears in a string
public static int countChar(String str, char target, int index) {
    // Base case: reached end of string
    if (index >= str.length()) {
        return 0;
    }

    // Recursive case: count current + count in rest
    int currentCount = (str.charAt(index) == target) ? 1 : 0;
    return currentCount + countChar(str, target, index + 1);
}

For tracing questions, the trick is the same as before: follow the index as it increases until it reaches the base case, then add up the returned values on the way back.

Recursion vs Iteration

Any recursive solution can be rewritten with a loop, and any loop can be rewritten with recursion. They are two ways to express repetition. The sumToN method above could just as easily be a for loop that adds numbers from 1 to n.

The exam does not ask you to choose one or convert between them in writing. It does expect you to recognize that recursion is repetition and that parameter values track progress the same way a loop control variable does.

How to Use This on the AP Computer Science A Exam

Code Tracing

• Read the base case first so you know when the recursion stops.
• Write each call on its own line as you go down toward the base case.
• Substitute returned values back up from the base case to the original call.
• If the method has two recursive calls, evaluate the left one completely before the right one.

Describing Behavior

• Trace two or three different inputs.
• Look at the pattern in the outputs to generalize what the method does overall.
• Match that pattern to the answer choice that describes the purpose, not just one specific result.

Common Trap

• A missing or unreachable base case means the recursion never stops. If you trace a call and the argument never moves toward the base case, that is a red flag.
• Do not assume the method finishes at the first recursive call. The original call is still paused and waiting to finish its own line.

Common Misconceptions

• "A recursive method has to have only one base case or one recursive call." A recursive method needs at least one of each, but it can have more than one base case or more than one recursive call.
• "All the calls share the same variables." Each call gets its own separate copy of the parameters and local variables. Changing n in one call does not change it in another.
• "The original call finishes as soon as it makes the recursive call." It pauses and waits. It only finishes after the recursive call returns a value.
• "Recursion is more powerful than loops." Recursion and iteration can solve the same problems. One is not stronger than the other, they are just different ways to repeat work.
• "I need to write recursive code for the exam." Writing recursive code is outside the scope of the exam. You only need to trace it and describe what it does.
• "Reaching the base case ends the whole method immediately." Reaching the base case ends that one call. The paused calls still need to finish and combine their results.

Related AP Computer Science A Guides

• 4.4 Traversing Arrays
• 4.5 Developing Algorithms Using Arrays
• 4.14 Searching
• 4.11 2D Arrays
• 4.13 Implementing 2D Array Algorithms
• 4.1 Ethical and Social Implications