AP CSA Practice Test: Recursion
AP CSA Practice Test: Recursion
Unit 4: Data Collections | 10 Questions | AP Computer Science A
mystery(4) return?public static int mystery(int n) {
if (n == 0) {
return 0;
}
return n + mystery(n - 1);
}
Explanation: mystery(4) = 4 + mystery(3) = 4 + 3 + mystery(2) = 4 + 3 + 2 + mystery(1) = 4 + 3 + 2 + 1 + mystery(0) = 4 + 3 + 2 + 1 + 0 = 10. This computes the sum 1+2+3+4.
Common Mistake: Not tracing all the way to the base case. Each call adds n to the result of mystery(n-1).
public static int broken(int n) {
return n + broken(n - 1);
}
Explanation: There is no base case, so the recursion never stops. Each call adds another frame to the call stack until memory runs out, causing StackOverflowError.
Common Mistake: Missing the lack of a base case. Every recursive method MUST have a base case to stop.
mystery("hello") return?public static String mystery(String s) {
if (s.length() <= 1) {
return s;
}
return mystery(s.substring(1)) + s.substring(0, 1);
}
Explanation: Each call moves the first character to the end: mystery("hello") = mystery("ello")+"h" = mystery("llo")+"e"+"h" = ... = "olleh". This reverses the string.
Common Mistake: Not tracing the full recursion. The first character is placed AFTER the result of the recursive call.
power(2, 5) return?public static int power(int base, int exp) {
if (exp == 0) {
return 1;
}
return base * power(base, exp - 1);
}
Explanation: power(2,5) = 2 * power(2,4) = 2 * 2 * power(2,3) = ... = 2*2*2*2*2*1 = 32. This computes base^exp recursively.
Common Mistake: Computing 2*5=10 (multiplication) instead of 2^5=32 (exponentiation).
fib called (including the initial call) for fib(5)?public static int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n-1) + fib(n-2);
}
Explanation: fib(5) calls fib(4)+fib(3). fib(4) calls fib(3)+fib(2). And so on. Drawing the call tree: fib(5)=1, fib(4)=1, fib(3)=2, fib(2)=3, fib(1)=5, fib(0)=3. Total = 15 calls.
Common Mistake: Underestimating the exponential growth. Fibonacci recursion makes many redundant calls.
count(12345) return?public static int count(int n) {
if (n == 0) {
return 0;
}
return 1 + count(n / 10);
}
Explanation: count(12345) = 1+count(1234) = 1+1+count(123) = 1+1+1+count(12) = 1+1+1+1+count(1) = 1+1+1+1+1+count(0) = 5. This counts the digits.
Common Mistake: Confusing n/10 with n%10. Division by 10 removes the last digit; modulo extracts it.
Explanation: Recursive methods can return any type (int, String, boolean, etc.) or be void. The only requirements are: a base case, progress toward it, and a problem that decomposes into subproblems.
Common Mistake: Thinking recursive methods must be void. Many recursive methods return values.
mystery(6) print?public static void mystery(int n) {
if (n > 0) {
System.out.print(n % 2);
mystery(n / 2);
}
}
Explanation: mystery(6): print 6%2=0, call mystery(3). mystery(3): print 3%2=1, call mystery(1). mystery(1): print 1%2=1, call mystery(0). Base case. Output: "011". This converts to binary but in reverse order.
Common Mistake: Reversing the output. The print happens BEFORE the recursive call, so digits print left-to-right as computed.
Explanation: Recursion is often more elegant and readable for problems like tree traversal, Fibonacci, or divide-and-conquer algorithms. However, it typically uses more memory (call stack) and can be slower than iteration.
Common Mistake: Thinking recursion is faster. It usually has overhead from call stack frames.
sumArr(arr, 0) return for {3, 7, 2}?public static int sumArr(int[] arr, int idx) {
if (idx == arr.length) {
return 0;
}
return arr[idx] + sumArr(arr, idx + 1);
}
Explanation: sumArr(arr,0) = 3 + sumArr(arr,1) = 3 + 7 + sumArr(arr,2) = 3 + 7 + 2 + sumArr(arr,3) = 3 + 7 + 2 + 0 = 12.
Common Mistake: Missing the base case. When idx equals arr.length, return 0 (no more elements).
Get in Touch
Whether you're a student, parent, or teacher — I'd love to hear from you.
Just want free AP CS resources?
Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.
Message Sent!
Thanks for reaching out. I'll get back to you within 24 hours.
Prefer email? Reach me directly at [email protected]