AP CS A: Recursion Patterns (with 4 worked examples)

Recursion is the AP CS A topic students fear most. It doesn't need to be that hard — almost every AP CS A recursion problem fits one of 4 patterns. Learn the patterns and recursion becomes mechanical.

Pattern 1 — Recursive accumulation (the most common)

You walk through a structure and accumulate a value. Examples: sum of a list, factorial, count of elements.

public static int sum(int[] arr, int i) {
  if (i == arr.length) return 0;        // base case
  return arr[i] + sum(arr, i + 1);      // recursive case
}

The base case is the empty (or finished) structure; return the identity (0 for sum, 1 for product).

Pattern 2 — Recursive search

You search a structure for an element that matches a condition. Examples: binary search, find max, check if value exists.

public static int findMax(int[] arr, int i) {
  if (i == arr.length - 1) return arr[i];   // base case: last element
  int restMax = findMax(arr, i + 1);
  return Math.max(arr[i], restMax);
}

Pattern 3 — Recursive transformation

You build a new structure from the input. Examples: reverse a string, copy an array, transform each element.

public static String reverse(String s) {
  if (s.length() <= 1) return s;            // base case
  return reverse(s.substring(1)) + s.charAt(0);
}

Pattern 4 — Recursive branching (the trickiest)

The recursive case calls itself more than once. Examples: fibonacci, tree traversal, recursive backtracking.

public static int fib(int n) {
  if (n <= 1) return n;                     // base case
  return fib(n - 1) + fib(n - 2);           // two recursive calls
}

Branching recursion is expensive (exponential without memoization). The AP exam usually doesn't test efficiency, but does test that you understand the logic.

Common AP CS A recursion FRQ mistakes

1. Missing or wrong base case. Infinite recursion is the #1 recursion bug.
2. Recursive call doesn't make progress. Each call must move toward the base case. foo(n) calling foo(n) doesn't make progress.
3. Forgetting to return the recursive call. foo(n - 1); without “return” does nothing useful.
4. Using void when you should return a value. Many recursion problems require returning the accumulated result.

Need a long-term AP Computer Science mentor, not just a one-off explanation? Learn about AP Computer Science mentorship at Palo Alto Mentor. Most of our students stay with the same mentor for 3–5 years.