1. What Is Recursion?

In Java, a method is called recursive when it calls itself as part of its own execution. Instead of solving a problem all at once, a recursive method breaks the problem into a smaller version of the same problem and delegates the smaller version back to itself.

A Classic Analogy

Imagine you are standing in a line and someone asks “How many people are ahead of you?” You can’t see the front of the line, so you ask the person directly in front of you. That person asks the person in front of them. This continues until someone is at the front and answers “zero.” Then the answer travels back — each person adds 1 to the answer they received and passes it back. That chain of asking and returning is exactly how recursion works.

Recursion vs. Iteration

Both recursion and iteration (loops) can solve many of the same problems. The AP exam sometimes asks you to compare the two or identify recursive and iterative equivalents. The key distinction:

2. The Two Requirements: Base Case & Recursive Case

Every correctly written recursive method has exactly two types of behavior built in. If either is missing or wrong, the method will fail — and the AP exam will ask you to identify which one is broken.

The Base Case

The base case is the condition under which the method stops calling itself and returns a value directly. Think of it as the exit ramp. Without it, the method runs forever.

The Recursive Case

The recursive case is the part of the method that calls itself. Critically, it must call itself with an argument that is closer to the base case than the current argument. If it doesn’t, the method will never terminate.

// Classic countdown — fully annotated
public static void countDown(int n)
{
    if (n == 0)                        // BASE CASE: stop here
    {
        System.out.println("Go!");
        return;
    }
    System.out.println(n);            // print current value
    countDown(n - 1);               // RECURSIVE CASE: smaller argument
}

What Makes a Recursive Case Valid?

• The argument passed to the recursive call must be different from the current argument.
• That difference must consistently move the argument toward the base case.
• If the argument is an integer counting down, each call must decrease it. If it’s a String being shortened, each call must use a shorter substring.

3. The Call Stack: How Java Tracks Recursion

When a method calls itself, Java doesn’t overwrite the current call — it pauses it and starts a brand-new execution of the method with the new argument. Each paused execution is stored in a stack frame on the call stack.

Think of the call stack like a stack of trays in a cafeteria. Each new recursive call pushes a new tray on top. Once the base case is reached, trays are removed one at a time from the top — each one using the return value from the tray above it to finish its own computation.

Stack Frame Contents

Each stack frame stores: the method’s local variables, its parameters, and the point in the code where execution should resume when this call returns. This is why recursion can use significant memory — deep recursion means many frames stacked up simultaneously.

The Unwinding Phase

Many students only think about the winding phase — the calls going deeper. But the unwinding phase is equally important. This is when the base case returns, and each paused call resumes, uses that return value, and returns its own result upward. A surprising amount of output can happen during unwinding, which is exactly what the AP exam tests.

4. Interactive Call Stack Visualizer

Select a method below and step through every stage of its execution. Watch frames push onto the call stack as calls go deeper, and pop off as return values propagate back up.

5. Step-by-Step Tracing: Worked Examples

The most reliable exam strategy is to write out a trace table on scratch paper. Below are three worked examples using the format the AP exam rewards.

Example A: Integer Accumulation

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

Question: What is returned by total(4)?

Strategy: Build the trace table. Each call waits until the call below it returns.

Example B: Print-After-Recurse (Order Reversal)

public static void display(int n)
{
    if (n > 0)
    {
        display(n - 1);               // recurse FIRST
        System.out.print(n + " ");   // then print
    }
}

Question: What does display(4) print?

This is a classic AP trap. The print statement comes after the recursive call, so printing only happens during the unwinding phase.

Example C: String Recursion

public static String shrink(String s)
{
    if (s.length() <= 1)
    {
        return s;
    }
    return s.charAt(0) + shrink(s.substring(1, s.length() - 1));
}

Question: What does shrink("ABCDE") return?

Each call strips the last character before recursing. The first character is prepended during unwinding.

6. Infinite Recursion and Common Errors

The AP exam frequently presents broken recursive methods and asks you to identify the error or select a fix. These are the four most common failure modes.

Error Type 1: Unreachable Base Case

public static int calc(int n)
{
    if (n == 0)          // checks for exactly 0
    {
        return 1;
    }
    return n * calc(n - 2);   // BUG: decrements by 2
}

Error Type 2: Recursive Call Moves Away from Base Case

public static void print(int n)
{
    if (n == 10)
    {
        System.out.println("done");
        return;
    }
    System.out.println(n);
    print(n - 1);    // BUG: going further from base case 10
}

Error Type 3: Missing Base Case Entirely

public static int add(int a, int b)
{
    return a + add(a - 1, b + 1);   // No base case at all!
}

Error Type 4: Off-by-One in Base Case

public static int power(int base, int exp)
{
    if (exp == 0)
    {
        return 1;
    }
    return base * power(base, exp - 1);
}

This one is actually correct! But if the base case were exp == 1 instead of exp == 0, then power(2, 0) would miss the base case and recurse into negative exponents forever. Off-by-one in the base case condition is a common AP exam distractor.

7. AP Exam Strategy: What You Will and Won’t Be Asked

What You Will Be Asked

• Trace a recursive method and predict the return value or console output
• Identify the base case in a given recursive method
• Identify a bug in a recursive method (unreachable base case, wrong direction)
• Determine what input would cause infinite recursion
• Select a fix that makes a broken recursive method work as intended
• Compare a recursive method to an iterative equivalent

The Exam-Proof Tracing Method

Use this four-step process on every recursive tracing question:

1. Locate the base case first. Before tracing, identify what stops the recursion and what value it returns.
2. Build a downward chain. Write each call with its argument. At each step, ask: does this argument satisfy the base case? If not, write the next call.
3. Mark the base case hit. Write the return value clearly.
4. Unwind upward. Substitute return values back into waiting calls, one level at a time. Do not skip levels.

public static int calc(int n)
{
    if (n == 1)
    {
        return 10;
    }
    return calc(n + 1) + n;
}

public static void proc(int n)
{
    if (n <= 0)
    {
        System.out.print("* ");
        return;
    }
    proc(n - 2);
    System.out.print(n + " ");
}

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

public static int digitCount(int n)
{
    if (n == 0)           // Line 3
    {
        return 0;
    }
    return 1 + digitCount(n / 10);
}

public static int recMethod(int n)
{
    if (n <= 0) { return 0; }
    return 3 + recMethod(n - 1);
}

public static int iterMethod(int n)
{
    int result = 0;
    for (int k = 1; k <= n; k++)
    {
        result += 3;
    }
    return result;
}

/** Precondition: 0 <= lo <= hi < arr.length */
public static boolean locate(int[] arr, int target, int lo, int hi)
{
    if (lo == hi)                       // Line 4
    {
        return false;                   // Line 6
    }
    else if (arr[lo] == target)
    {
        return true;
    }
    else
    {
        return locate(arr, target, lo + 1, hi);
    }
}

Key Vocabulary

Frequently Asked Questions