Recursion — AP Computer Science A CS A Study Guide

For: AP Computer Science A candidates sitting AP Computer Science A.

Covers: Base and recursive cases, tracing recursive calls, recursion vs iteration, recursive binary search, and common recursion problems including factorial and Fibonacci sequences.

You should already know: Basic Java or any other procedural-language programming.

A note on the practice questions: All worked questions in the "Practice Questions" section below are original problems written by us in the AP Computer Science A style for educational use. They are not reproductions of past College Board papers and may differ in wording, numerical values, or context. Use them to practise the technique; cross-check with official College Board mark schemes for grading conventions.

1. What Is Recursion?

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 writing iterative loops to repeat operations, recursive code breaks problems into identical subproblems, eliminating the need for manual counter management and temporary storage variables in many cases. Recursion is tested explicitly in Unit 10 of the AP CS A Course and Exam Description, making up 5-7.5% of your final exam score. Common synonyms include recursive procedure and self-referential function.

2. Base case and recursive case

Every valid recursive method has two non-negotiable components, and exam questions frequently ask you to identify missing or incorrect versions of either. First, the base case: the simplest instance of the problem where the output is known immediately, with no further recursive calls required. Omitting a base case, or writing a base case that is never reached, causes a StackOverflowError, as the JVM will continue adding new method calls to the call stack until it runs out of allocated memory. Second, the recursive case: the segment of the method where it calls itself with a modified, smaller input that moves incrementally closer to the base case. Each recursive call reduces the scope of the problem until the base case is triggered.

Worked Example: Recursive Sum of First n Positive Integers

public static int sum(int n) {
 // Base case: sum of first 1 integer is known
 if (n == 1) {
 return 1;
 }
 // Recursive case: sum(n) = n + sum of first n-1 integers
 return n + sum(n - 1);
}

For input n=3, sum(3) calls sum(2), which calls sum(1) (the base case). sum(1) returns 1, sum(2) returns 2 + 1 = 3, and sum(3) returns 3 + 3 = 6. Exam tip: Always write the base case first when building recursive methods for free response questions to avoid forgetting it under time pressure.

3. Tracing recursive calls

Tracing is the process of mapping every recursive call, its input parameters, and its return value to calculate the final output of a recursive method. This is one of the most frequently tested recursion skills on the AP CS A exam, appearing in 2-3 multiple choice questions per test on average. When tracing, remember that all method calls are stored in the JVM call stack, a last-in-first-out (LIFO) data structure. Calls are pushed to the top of the stack when initiated, and popped off the stack once they return a value. You will only get valid return values once you reach the base case, so you must work backwards up the stack to compute final outputs.

Worked Trace Example: Factorial of 4

We use the standard factorial method for this trace:

public static int factorial(int n) {
 if (n == 0) return 1; // Base case
 return n * factorial(n - 1);
}

1. Push factorial(4) to stack: n=4, not base case, call factorial(3)
2. Push factorial(3) to stack: n=3, not base case, call factorial(2)
3. Push factorial(2) to stack: n=2, not base case, call factorial(1)
4. Push factorial(1) to stack: n=1, not base case, call factorial(0)
5. Push factorial(0) to stack: n=0, base case, return 1, pop from stack
6. factorial(1) receives 1, returns 1 * 1 = 1, pop from stack
7. factorial(2) receives 1, returns 2 * 1 = 2, pop from stack
8. factorial(3) receives 2, returns 3 * 2 = 6, pop from stack
9. factorial(4) receives 6, returns 4 * 6 = 24, pop from stack Final output: 24. Exam tip: Write all calls in a vertical list first, then fill in return values starting from the base case to avoid calculation errors.

4. Recursion vs iteration

Every recursive solution can be rewritten as an iterative (loop-based) solution, and vice versa. The exam often asks you to identify equivalent recursive and iterative implementations of the same function, so understanding their differences is critical.

Worked Example: Iterative vs Recursive Sum

Equivalent iterative implementation of the sum function from Section 2:

public static int sumIterative(int n) {
 int total = 0;
 for (int i = 1; i <= n; i++) {
 total += i;
 }
 return total;
}

For input n=1000, the recursive sum method will throw a StackOverflowError on most standard JVMs, while the iterative version will run without issues. Exam note: The exam will never ask you to argue for one approach over the other for production use, but you may be asked to identify performance limits of recursive implementations for large inputs.

5. Recursive search — binary search

Binary search is a divide-and-conquer search algorithm that finds the position of a target value within a sorted array, and it is the most commonly tested recursive application on the AP CS A exam. It works by repeatedly dividing the search interval in half, reducing the problem size by 50% with each call. The recursive implementation has two base cases:

1. If the low index of the search interval exceeds the high index, the target is not present, return -1
2. If the middle element of the interval equals the target, return the middle index The recursive case splits the interval: if the target is smaller than the middle element, search the left half; if larger, search the right half.

Recursive Binary Search Code

public static int recursiveBinarySearch(int[] sortedArr, int target, int low, int high) {
 // Base case 1: target not found
 if (low > high) {
 return -1;
 }
 int mid = (low + high) / 2;
 // Base case 2: target found
 if (sortedArr[mid] == target) {
 return mid;
 }
 // Recursive cases
 else if (target < sortedArr[mid]) {
 return recursiveBinarySearch(sortedArr, target, low, mid - 1);
 } else {
 return recursiveBinarySearch(sortedArr, target, mid + 1, high);
 }
}

Worked Example

Search for target 7 in the sorted array [1,3,5,7,9,11,13]:

• Initial call: low=0, high=6, mid=3, sortedArr[3] = 7, return index 3 Search for target 4 in the same array:
• Initial call: low=0, high=6, mid=3, 7>4, search left half low=0, high=2
• Next call: mid=1, 3<4, search right half low=2, high=2
• Next call: mid=2, 5>4, search low=2, high=1, which triggers base case, return -1 Critical exam trap: Binary search only works on sorted arrays. Multiple choice questions often present unsorted input arrays and ask if binary search will return a valid result, so always check for sorted input first.

6. Common recursion problems — factorial, Fibonacci

Two of the most frequently tested recursive problems on the exam are factorial and Fibonacci sequence calculations, and you are expected to write their recursive implementations from memory for free response questions.

Factorial

The 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$. The recursive formula is: $$n! = \begin{cases} 1 & n = 0 \ n \times (n-1)! & n > 0 \end{cases}$$ We traced the factorial of 4 in Section 3, and it has a time complexity of $O(n)$ as it makes exactly n recursive calls.

Fibonacci Sequence

The Fibonacci sequence is defined such that the first two terms are 0 and 1, and each subsequent term is the sum of the two preceding terms. The recursive formula per AP CS A conventions is: $$F(n) = \begin{cases} 0 & n = 0 \ 1 & n = 1 \ F(n-1) + F(n-2) & n \geq 2 \end{cases}$$ Recursive Fibonacci code:

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

For $n=4$, the output is 3. Note that recursive Fibonacci has a time complexity of $O(2^n)$, as it recalculates the same values hundreds of times for larger n. Exam questions frequently ask about this inefficiency, so be prepared to note that iterative Fibonacci is far more performant for large inputs.

7. Common Pitfalls (and how to avoid them)

• Pitfall: Omitting a base case, or writing a base case that is never reached. Why students do it: They rush writing the recursive case and forget termination conditions, or modify input to move away from the base case (e.g., calling sum(n+1) instead of sum(n-1)). Correct move: Write the base case first, and verify every recursive call brings the input closer to the base case.
• Pitfall: Using binary search on unsorted arrays. Why students do it: They memorize binary search code but forget the input requirement. Correct move: Explicitly state that the input array must be sorted every time you write binary search for free response questions.
• Pitfall: Tracing recursive calls top-down instead of bottom-up. Why students do it: They try to calculate return values as they write calls, instead of waiting for the base case. Correct move: List all recursive calls first, then compute return values starting from the base case and working up the stack.
• Pitfall: Mixing up Fibonacci base cases. Why students do it: Some external sources start the Fibonacci sequence at $F(1)=1,F(2)=1$. Correct move: Use the AP CS A standard base cases $F(0)=0,F(1)=1$ unless the question explicitly states otherwise.
• Pitfall: Ignoring stack overflow limits for large inputs. Why students do it: They test recursive code with small n values and assume it works for all inputs. Correct move: Prefer iterative solutions for n > 1000, and note the stack overflow limitation of recursion if asked in free response.

8. Practice Questions (AP Computer Science A Style)

Question 1 (Multiple Choice)

What is the output of the following recursive method when called with mystery(5)?

public static int mystery(int n) {
 if (n <= 1) return 2;
 return mystery(n-1) * 3;
}

A) 6 B) 54 C) 162 D) 486

Solution: Trace the calls: mystery(5) = mystery(4)*3, mystery(4)=mystery(3)*3, mystery(3)=mystery(2)*3, mystery(2)=mystery(1)*3, mystery(1)=2. Working backwards: mystery(2)=6, mystery(3)=18, mystery(4)=54, mystery(5)=162. Correct answer: C.

Question 2 (Free Response)

Write a recursive method called power that takes two positive integers base and exponent, and returns base raised to the power of exponent. For example, power(2,3) returns 8. You may not use loops or the built-in Math.pow method.

Solution: Base case: Any number raised to the power of 0 is 1. Recursive case: $bas{e}^{exponent}=base\ast bas{e}^{exponent-1}$

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

Verification: power(2,3) = 2 * power(2,2) = 2*2*power(2,1) = 2*2*2*power(2,0) = 8*1 = 8, which matches the example.

Question 3 (Multiple Choice)

Which of the following is a valid difference between recursive and iterative implementations of the same algorithm? A) Recursive implementations always run faster B) Iterative implementations use call stack memory for each repetition C) Recursive implementations require a base case to terminate D) Iterative implementations are always more readable

Solution: A is incorrect: recursion is slower due to method call overhead. B is incorrect: recursive implementations use call stack memory, iterative implementations use heap memory for variables. D is incorrect: recursive code is often more readable for divide-and-conquer problems. Correct answer: C.

9. Quick Reference Cheatsheet

10. What's Next

Recursion is a foundational skill for all remaining advanced topics in the AP CS A syllabus, including 2D array traversal, ArrayList operations, and especially binary tree traversals (pre-order, in-order, and post-order traversals are almost exclusively implemented recursively on the exam). Mastering recursive tracing and base case identification now will save you significant time when studying these later units, as many of the most efficient and concise solutions for these problems rely on recursive logic. Recursion also appears regularly in free response questions that require you to traverse nested data structures, so a strong grasp of this topic is directly correlated with higher exam scores.

If you're struggling with tracing recursive calls, identifying base cases, or any other part of this topic, you can ask Ollie for personalized practice problems, step-by-step trace walkthroughs, or clarifications of any concept by visiting the homepage. You can also test your knowledge with our full AP CS A recursion practice quiz, aligned directly to the College Board CED requirements and marked with official grading rubrics.