AP Computer Science A Recursion — Worked Answer Explanations

Unit 10 · 12 questions explained

Below is a complete answer key for our AP Computer Science A Recursion practice questions. For each question you'll find the correct choice, a full written explanation of how to get there, and — for every wrong answer — a short note on exactly why it's tempting and where it goes wrong. Reading these straight through is one of the fastest ways to find the gaps in a unit before exam day.

Prefer to test yourself first? Take the timed Recursion practice test and come back here to review, or head back to the Recursion unit overview.

In-content ad

Question 1 · Easy
What is the base case in the following recursive method?
```
public static int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}
```
- A
  return n * factorial(n - 1)
  Why not A: That is the recursive case; it makes a call to factorial with a smaller argument.
- B
  if (n == 0) return 1Correct
- C
  There is no base case; this method will recurse forever.
  Why not C: n == 0 is the base case that stops the recursion.
- D
  n * factorial(n - 1) where n == 1
  Why not D: When n == 1 the base case has not fired yet; the method calls factorial(0), which then hits the base case.
Explanation
The base case is the condition that stops recursion without making another recursive call. Here, if (n == 0) return 1 terminates the chain. The recursive case n * factorial(n - 1) runs only when n > 0.

Key takeaway
The base case stops recursion by returning directly; every recursive method must have at least one base case.
Question 2 · Easy
What is the output of the following code?
```
public static void countdown(int n) {
    if (n == 0) {
        System.out.println("Go!");
        return;
    }
    System.out.println(n);
    countdown(n - 1);
}
// Called with:
countdown(3);
```
- A
  Go! 1 2 3
  Why not A: The print statements execute before the recursive call, so numbers appear before "Go!", not after.
- B
  3 2 1 Go!Correct
- C
  1 2 3 Go!
  Why not C: Numbers print in the order the calls are made (3 first, then 2, then 1), not in reverse.
- D
  3 2 1
  Why not D: "Go!" is printed when n == 0; it is part of the base case output.
Explanation
Each call prints n, then recurses with n-1. countdown(3) prints 3, calls countdown(2) which prints 2, calls countdown(1) which prints 1, calls countdown(0) which prints "Go!". Output: 3 2 1 Go!.

Key takeaway
When printing before the recursive call, values appear in the order the calls are made (largest first for a decreasing recursion).
Question 3 · Easy
What value does the following method return when called with sum(4)?
```
public static int sum(int n) {
    if (n == 0) return 0;
    return n + sum(n - 1);
}
```
- A
  4
  Why not A: Only returned n at the outermost call, ignoring the recursive accumulation.
- B
  8
  Why not B: Doubled n (4*2=8) instead of summing 4+3+2+1+0.
- C
  10Correct
- D
  24
  Why not D: Computed 4! (432*1=24) by multiplying instead of adding.
Explanation
sum(4) = 4 + sum(3) = 4 + 3 + sum(2) = 4 + 3 + 2 + sum(1) = 4 + 3 + 2 + 1 + sum(0) = 4 + 3 + 2 + 1 + 0 = 10.

Key takeaway
Recursive summation: sum(n) = n + sum(n-1) with base case sum(0) = 0 computes 1+2+...+n = n*(n+1)/2.
Question 4 · Easy
What is the output of the following code?
```
public static void mystery(int n) {
    if (n <= 0) return;
    mystery(n - 1);
    System.out.println(n);
}
// Called with:
mystery(3);
```
- A
  3 2 1
  Why not A: The print executes after the recursive call, so values print as calls return (smallest first).
- B
  1 2 3Correct
- C
  3 2 1 0
  Why not C: When n == 0 the method returns immediately without printing; 0 is never printed.
- D
  0 1 2 3
  Why not D: 0 is not printed because the base case (n <= 0) returns before reaching the println.
Explanation
The recursive call comes BEFORE the print statement. mystery(3) calls mystery(2), which calls mystery(1), which calls mystery(0) (returns immediately). Then 1 prints, then 2 prints, then 3 prints as each frame returns. Output: 1 2 3.

Key takeaway
Printing after the recursive call reverses the order; values appear as the call stack unwinds from base case back up.
Question 5 · Easy
The Fibonacci sequence is defined as fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2) for n≥2. What does the following method return for fib(5)?
```
public static int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}
```
- A
  4
  Why not A: Computed fib(4)=3 + fib(3)=2 incorrectly, or only traced one level of recursion.
- B
  5Correct
- C
  8
  Why not C: Returned fib(6)=8 by advancing the index by one.
- D
  10
  Why not D: Added all integers from 1 to 4 instead of following the Fibonacci recurrence.
Explanation
Tracing: fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=fib(4)+fib(3)=3+2=5.

Key takeaway
Fibonacci via recursion has two base cases (n=0 and n=1); fib(5)=5 is the sixth Fibonacci number.
Question 6 · Medium
A recursive method and an iterative method both solve the same problem. Which of the following is a trade-off of choosing recursion over iteration?
- A
  Recursive solutions always run faster than iterative ones.
  Why not A: Recursion typically has more overhead due to repeated method calls and call-stack management; it is rarely faster.
- B
  Recursion can lead to a StackOverflowError if the input is too large or the base case is missing.Correct
- C
  Iterative solutions cannot express problems like factorial or Fibonacci.
  Why not C: Factorial and Fibonacci are easily expressed iteratively with a loop.
- D
  Recursive methods cannot return values.
  Why not D: Recursive methods can return values; most recursive examples (factorial, fib) do exactly that.
Explanation
Each recursive call adds a frame to the call stack. With large inputs or a missing/incorrect base case, the stack overflows (StackOverflowError). Recursion can produce elegant code for inherently recursive problems, but the call-stack overhead is a real cost.

Key takeaway
Recursion risks StackOverflowError on deep inputs; always verify the base case terminates and the problem size decreases each call.
Question 7 · Medium
What does the following method return when called with mystery(5)?
```
public static int mystery(int n) {
    if (n == 1) return 0;
    return 1 + mystery(n / 2);
}
```
- A
  2Correct
- B
  3
  Why not B: Traced mystery(8) instead of mystery(5), getting one extra level of recursion.
- C
  5
  Why not C: Returned n itself rather than tracing the recursive calls.
- D
  1
  Why not D: Stopped tracing at mystery(2) without adding the final 1 + mystery(1)=0.
Explanation
Trace: mystery(5) = 1 + mystery(2) [5/2=2 in integer division]. mystery(2) = 1 + mystery(1) [2/2=1]. mystery(1) = 0. Unwinding: mystery(2) = 1+0 = 1. mystery(5) = 1+1 = 2. This method counts how many times you can halve n before reaching 1 (floor of log base 2).

Key takeaway
Halving-style recursion runs in O(log n) steps; trace integer division carefully at each call.
Question 8 · Medium
Consider the following recursive method:
```
public static int sumArray(int[] arr, int index) {
    if (index == arr.length) return 0;
    return arr[index] + sumArray(arr, index + 1);
}
```
What is returned by sumArray(new int[]{3, 1, 4, 1, 5}, 0)?
- A
  3
  Why not A: Returned only the first element (index 0) without continuing the recursion.
- B
  9
  Why not B: Summed the first four elements (3+1+4+1=9) and stopped before reaching index 4.
- C
  14Correct
- D
  15
  Why not D: Added an extra 1, perhaps treating the length (5) as an element.
Explanation
sumArray processes arr[0]=3, arr[1]=1, arr[2]=4, arr[3]=1, arr[4]=5, then hits the base case (index==5). Sum = 3+1+4+1+5 = 14.

Key takeaway
Recursive array traversal with an index parameter processes one element per call; base case fires when index reaches the array length.
Question 9 · Hard
Which of the following recursive methods contains a flaw that would cause infinite recursion for the call badRecurse(5)?
```
// Option A
public static int badRecurse(int n) {
    if (n == 0) return 0;
    return n + badRecurse(n + 1);
}
```
- A
  The base case n == 0 is never reached because each call increases n.Correct
- B
  The base case is missing entirely.
  Why not B: A base case exists (n == 0); the problem is that the recursive argument moves away from it, not that it is absent.
- C
  The method returns the wrong type and will cause a compile error.
  Why not C: The return type int matches the method signature and the returned expressions; no compile error.
- D
  The recursion is fine; badRecurse(5) returns a large positive number.
  Why not D: The argument grows without bound (5, 6, 7, ...), so the base case n==0 is never reached and a StackOverflowError occurs.
Explanation
badRecurse(5) calls badRecurse(6), then badRecurse(7), and so on. The argument increases each call, so n is never 0 and the base case is never triggered. This causes a StackOverflowError due to infinite recursion.

Key takeaway
The recursive argument must move toward the base case on every call; moving away from it causes infinite recursion.
Question 10 · Hard
What is the output of the following code?
```
public static String reverse(String s) {
    if (s.length() == 0) return "";
    return reverse(s.substring(1)) + s.charAt(0);
}
System.out.println(reverse("abc"));
```
- A
  abc
  Why not A: Assumed the characters are appended in forward order, but charAt(0) is appended after the recursive result, which processes the tail first.
- B
  bca
  Why not B: Misapplied substring or charAt indexing, rotating rather than reversing.
- C
  cbaCorrect
- D
  cab
  Why not D: Moved the first character to the end without correctly reversing the rest of the string.
Explanation
reverse("abc") = reverse("bc") + 'a'. reverse("bc") = reverse("c") + 'b'. reverse("c") = reverse("") + 'c' = "" + 'c' = "c". So: "c" + 'b' = "cb", then "cb" + 'a' = "cba".

Key takeaway
String reversal via recursion: recurse on the tail (substring(1)), then append the head character at the end.
Question 11 · Hard
Consider the following method:
```
public static int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}
```
How many times total is power called (including the initial call) when evaluating power(2, 4)?
- A
  4
  Why not A: Counted only the recursive calls (exp=3,2,1,0) and omitted the initial call (exp=4).
- B
  5Correct
- C
  8
  Why not C: Computed 2^3=8 and used that as the call count.
- D
  16
  Why not D: Used the return value (2^4=16) as the call count.
Explanation
The call chain is power(2,4) → power(2,3) → power(2,2) → power(2,1) → power(2,0). That is 5 calls total: exp=4, 3, 2, 1, and the base case at exp=0.

Key takeaway
For a linear recursion with decrement-by-one, the total call count equals the initial value of the parameter plus 1 (for the base case call).
Question 12 · Hard
A programmer wants to use recursion to check if a string is a palindrome. Which recursive definition is correct?
```
public static boolean isPalin(String s) {
    if (s.length() <= 1) return true;
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalin(s.substring(1, s.length() - 1));
}
```
What does isPalin("racecar") return?
- A
  false, because 'r' and 'r' are at the same position.
  Why not A: First and last characters matching is a condition for returning true, not false.
- B
  trueCorrect
- C
  A StringIndexOutOfBoundsException is thrown.
  Why not C: The base case (length <= 1) prevents accessing invalid indices; the substring always reduces in size.
- D
  false, because the middle character 'e' has no pair.
  Why not D: When the string reaches a single character (length 1), the base case returns true; odd-length palindromes are handled correctly.
Explanation
isPalin("racecar"): 'r'=='r' → isPalin("aceca"). 'a'=='a' → isPalin("cec"). 'c'=='c' → isPalin("e"). Length 1 → returns true. All characters matched, so "racecar" is a palindrome.

Key takeaway
Recursive palindrome check strips matching outer characters, recursing on the inner substring until length ≤ 1.