Recursion — AP Computer Science A
1. Core Recursion Structure ★★☆☆☆ ⏱ 3 min
Recursion is a problem-solving technique where a method calls itself with a smaller input subset to solve a larger instance of the same problem. Instead of iterative loops, recursive code breaks problems into identical subproblems, simplifying many common algorithm designs. Recursion makes up 5-7.5% of your final AP CS A exam score.
Exam tip: Always write the base case first when constructing recursive methods for free response questions to avoid forgetting it under time pressure.
2. Tracing Recursive Calls ★★☆☆☆ ⏱ 4 min
Tracing recursive calls to get a final output is one of the most frequently tested recursion skills, appearing in 2-3 multiple choice questions per AP CS A exam. All recursive calls are stored in the JVM call stack, a last-in-first-out (LIFO) structure. You must work backwards from the base case to get the final result, since return values only become available once the base case is hit.
Exam tip: Write all calls in a vertical list first, then fill in return values starting from the base case to avoid calculation errors.
3. Recursion vs Iteration ★★☆☆☆ ⏱ 3 min
Any recursive solution can be rewritten as an iterative (loop-based) solution, and vice versa. The AP CS A exam often asks to identify equivalent implementations and compare the two approaches.
4. Common Tested Recursive Algorithms ★★★☆☆ ⏱ 6 min
Recursive binary search is the most commonly tested recursive application on the AP CS A exam. It is a divide-and-conquer algorithm to find a target in a sorted array, reducing the search interval by half with each recursive call.
The standard implementation is: ```java public static int recursiveBinarySearch(int[] sortedArr, int target, int low, int high) { if (low > high) return -1; int mid = (low + high) / 2; if (sortedArr[mid] == target) return mid; else if (target < sortedArr[mid]) return recursiveBinarySearch(sortedArr, target, low, mid - 1); else return recursiveBinarySearch(sortedArr, target, mid + 1, high); } ```
Factorial of a non-negative integer $n$, written $n!$, is the product of all positive integers less than or equal to $n$. By definition, $0! = 1$.
n! = \begin{cases} 1 & n = 0 \\ n \times (n-1)! & n > 0 \end{cases}
Recursive factorial has a time complexity of $O(n)$, as it makes exactly n recursive calls.
The Fibonacci sequence follows AP CS A conventions with base cases $F(0)=0$ and $F(1)=1$, where each subsequent term is the sum of the two preceding terms.
F(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F(n-1) + F(n-2) & n \geq 2 \end{cases}
The recursive implementation is: ```java public static int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacci(n-1) + fibonacci(n-2); } ``` Recursive Fibonacci has a time complexity of $O(2^n)$, because it repeatedly recalculates the same subproblem values, a fact commonly tested on the exam.
Common Pitfalls
Why: Students rush to write the recursive case and forget termination conditions, or modify input to move away from the base case
Why: Students memorize binary search code but forget the core input requirement
Why: Students try to compute outputs as they write calls, instead of waiting for the base case to resolve values
Why: Conflicting definitions from external sources lead to incorrect base cases on the exam
Why: Students test recursive code with small n and assume it works for all inputs