Recursion Tracing Guide for AP CSA 2026

What You Need to Know

Recursion tracing = predicting exactly what a recursive method does (return value and/or output) by following the chain of method calls until a base case, then unwinding returns back up the call stack.

Why AP CSA cares:

• FRQs and MCQs often give you a recursive method and ask for the output, return value, or how many times something runs.
• The “gotchas” are usually about when code executes (before vs after the recursive call), what gets returned, and whether you hit the base case.

Core idea (what recursion must have):

• Base case: a condition where the method stops calling itself.
• Recursive step: calls itself on a “smaller” or “closer” input.
• Progress toward base: each call must move closer to the base case (otherwise stack overflow).

Two recursion “flavors” you’ll trace on AP CSA:

1. Return recursion: method returns a value computed from recursive results.
2. Side-effect recursion: method prints, mutates arrays/strings/fields, etc., often returning void.

Critical reminder: Each recursive call gets its own stack frame (its own copy of parameters and local variables). Values don’t “change everywhere” unless you mutate a shared object (like an array).

Step-by-Step Breakdown

A. Universal tracing routine (works for almost everything)

1. Identify the base case(s)
   • Find the if condition(s) that stop recursion.
   • Determine what the method returns or does at the base case.
2. Track the “shrinking” input
   • Write how parameters change each call: n - 1, index + 1, str.substring(1), etc.
3. Create a call stack table (fast + reliable)
   • Columns you want:
     • Depth (0, 1, 2, …)
     • Arguments (parameter values)
     • What happens before the recursive call (prints, updates, etc.)
     • Returned value (once known)
4. Go down until you hit the base case
   • Don’t try to “solve” mid-way. Just push calls.
5. Unwind (return back up)
   • Compute returns using the exact return expression at each level.
   • For printing/mutations after the recursive call, do them during unwinding.
6. If there are multiple recursive calls, evaluate left-to-right
   • Java evaluates operands left-to-right.
   • Example: f(n-1) + f(n-2) computes f(n-1) completely before starting f(n-2).

B. Mini-walkthrough: return recursion

public static int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);
}

Trace fact(4):

• Calls go down: fact(4) -> fact(3) -> fact(2) -> fact(1) -> fact(0)
• Base returns 1
• Unwind:
  • fact(1) = 1 * 1 = 1
  • fact(2) = 2 * 1 = 2
  • fact(3) = 3 * 2 = 6
  • fact(4) = 4 * 6 = 24
    Final answer: $24$

C. Mini-walkthrough: side-effect recursion (print order)

public static void mystery(int n) {
    if (n <= 0) {
        System.out.print("A");
    } else {
        System.out.print("B");
        mystery(n - 1);
        System.out.print("C");
    }
}

Trace mystery(2):

• Going down (before recursion): prints B (at n=2), then B (at n=1)
• Base (n=0): prints A
• Unwinding (after recursion): prints C (returning to n=1), then C (returning to n=2)
  Output: BBACC

Print-before-recursion = happens on the way down. Print-after-recursion = happens on the way up.

Key Formulas, Rules & Facts

Tracing rules you use constantly

Base-case patterns you should recognize (AP CSA common)

“Execution timing” cheat facts

• Code before the recursive call executes in the same order as the calls are made.
• Code after the recursive call executes in reverse order as calls return.
• A return statement immediately ends the current call frame.

Examples & Applications

Example 1: Return recursion with a twist (non-factorial)

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

Find sumTo(7).

• Calls: 7 -> 5 -> 3 -> 1 -> -1 (base)
• Base returns 0
• Unwind: sumTo(1)=1, sumTo(3)=4, sumTo(5)=9, sumTo(7)=16
  Answer: $16$

Key insight: parameter decreases by $2$ each time; base is n <= 0.

Example 2: Print order (classic AP CSA trap)

public static void show(int n) {
    if (n == 0) {
        System.out.print(0);
    } else {
        System.out.print(n);
        show(n - 1);
        System.out.print(n);
    }
}

Trace show(3):

• Down prints: 3 2 1
• Base prints: 0
• Up prints: 1 2 3
  Output: 3210123

Key insight: symmetric printing because the same n prints before and after.

Example 3: Recursion on strings (substring tracing)

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

Compute everyOther("ABCDE").

• "ABCDE" -> "CDE" -> "E" (base)
• Returns: "A" + ("C" + "E") = "ACE"
  Answer: ACE

Trick: substring(2) drops the first two characters each call.

Example 4: Array recursion (shared mutation + index)

public static void zeroNeg(int[] arr, int i) {
    if (i >= arr.length) return;
    if (arr[i] < 0) arr[i] = 0;
    zeroNeg(arr, i + 1);
}

Given int[] a = {2, -5, -1, 7}; zeroNeg(a, 0);
Final array: {2, 0, 0, 7}

Key insight: arr is shared across calls; each frame changes one index then recurses.

Example 5: Two recursive calls (tree recursion)

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

Find f(4).

• f(4) = f(3) + f(2)
• f(3) = f(2) + f(1)
• f(2) = f(1) + f(0)
  Compute bottom-up:
• f(0)=0, f(1)=1
• f(2)=1
• f(3)=2
• f(4)=3
  Answer: $3$

Tracing tip: write a mini-tree or compute with a small table of known values.

Common Mistakes & Traps

1. Missing the true base case

   • What goes wrong: You stop at the first if you see, but it doesn’t actually stop recursion for the given input.
   • Why it’s wrong: If the base condition isn’t met, calls keep going.
   • Fix: Plug in the starting value and see if the condition becomes true eventually.

2. Off-by-one base conditions

   • What goes wrong: Using n == 0 when calls go n - 2 and might skip exactly zero; or using i == arr.length vs i >= arr.length.
   • Why it’s wrong: You can overshoot the base and recurse forever or hit an exception.
   • Fix: Use inequality bases (<=, >=) when stepping might skip the exact boundary.

3. Confusing print order (down vs up)

   • What goes wrong: You list output in the order you read the code.
   • Why it’s wrong: Lines after the recursive call don’t run until the recursion returns.
   • Fix: Mark lines as PRE (before call) vs POST (after call). PRE prints on the way down; POST prints on the way up.

4. Forgetting to use the recursive return value

   • What goes wrong: Thinking the recursive call “updates” a variable automatically.
   • Why it’s wrong: If you don’t return it or combine it, it’s computed then thrown away.
   • Fix: In return recursion, ensure the recursive call is part of the returned expression.

5. Mutating parameters vs reassigning locals

   • What goes wrong: Thinking arr = new int[...] inside recursion changes the caller’s array.
   • Why it’s wrong: Reassigning a parameter only changes that local reference.
   • Fix: Mutate arr[i] = ... if you want persistent changes; avoid reassigning the parameter.

6. Not tracking multiple recursive calls separately

   • What goes wrong: Treating f(n-1) + f(n-2) like one call chain.
   • Why it’s wrong: It branches into two full computations.
   • Fix: Trace left call fully, then right call fully, then combine.

7. Assuming recursion “remembers” updated locals across frames

   • What goes wrong: You increment a local variable and expect it to keep incrementing across calls.
   • Why it’s wrong: Each frame has its own copy.
   • Fix: If you need accumulating state, pass it as a parameter (common with helper methods) or use a shared field (but then trace side effects carefully).

8. Stack overflow / infinite recursion from no progress

   • What goes wrong: Recursive call doesn’t move toward base (e.g., mystery(n) calls mystery(n) or mystery(n+1) with base n==0).
   • Why it’s wrong: Base case never reached.
   • Fix: Verify a monotonic move toward the base each call.

Memory Aids & Quick Tricks

Quick Review Checklist

• [ ] I can point to the base case and state exactly what it returns/does.
• [ ] I can show how each call moves toward the base case.
• [ ] I trace with a call stack table (depth + args + return + output).
• [ ] I know PRE code runs on the way down; POST code runs on the way up.
• [ ] I treat each call’s locals as separate copies.
• [ ] I remember arrays/objects are shared, so mutations persist.
• [ ] For f(a) + f(b), I evaluate left-to-right and combine after both return.
• [ ] I can handle edge bases: empty string, i >= length, n <= 0, start > end.

You’ve got this: if you can force yourself to trace mechanically (down to base, then unwind), recursion questions become predictable.