A recursion multiple choice problem with a print statement can often be solved without fully analyzing or tracing the method.
Technique for recursive methods with print statements
Address infinite recursion first
If the answer choices include infinite recursion as a possibility, address it first. Does the method have a base case (or base cases)? Does the recursive call (or calls) get closer to and eventually hit the base case(s)?
Not all infinitely recursive methods with print statements actually print anything. If the method is infinitely recursive, but the all the print statements are after the recursive call(s), the method might not print anything.
Position of print statement(s) relative to recursive call(s)
Once infinite recursion has been eliminated as a possibility, consider the position of the print statement(s) relative to the recursive call(s). It is often possible to determine the first and/or last thing the method will ever print. This can be enough to eliminate answer choices, potentially all but 1.
In other cases, it’s possible to determine something about the output, such as that a particular value will appear in the middle, or that a particular value will or will not ever be printed. This can eliminate answer choices, potentially all but 1.
Exercises
Exercise 1
Consider method mystery.
public static void mystery(int x)
{
if(x >= 0)
{
mystery(x - 1);
System.out.println(x);
}
}
Which of the following describes the sequence of integers output? (Ignore line breaks.)
(A) x, x - 1, x - 2 ... 1
(B) x, x - 1, x - 2 ... 1, 0
(C) x - 1, x - 2 ... 1, 0
(D) 0, 1 ... x - 1, x
(E) 1, 2 ... x - 1, x
Exercise 2
Consider method mystery.
public static void mystery(String str, int len)
{
if(str.length() < len)
{
System.out.print(str);
return;
}
System.out.print(str.substring(0, len));
mystery(str.substring(len), len);
System.out.print(str.substring(0, len));
}
Which of the following describes what is printed by the call below?
mystery("abcdef", 3);
(A) abcdefdefabc
(B) abcabcdefdef
(C) defabcabcdef
(D) Many values are printed because of infinite recursion.
(E) Nothing is printed because of infinite recursion.
Exercise 3
Consider method mystery.
public static void mystery(String str)
{
if(str.length() < 3)
{
return;
}
mystery(str.substring(3) + str.substring(0, 3));
System.out.println(str.substring(0, 3));
}
Which of the following describes what is printed by the call below?
mystery("abcdefhig");
(A) higdefabc
(B) abcdefhig
(C) abcdefhighigdefabc
(D) Many values are printed because of infinite recursion.
(E) Nothing is printed because of infinite recursion.
Additional examples from common resources
2014 AP CS A Course Description MC #14
Question 14 (PDF page 34, numbered page 30) from the 2014 AP CS A Course Description sample multiple choice illustrates the value of this approach.
Try Question 14 then see the explanation in my 2014 Course Description MC Explanations.
Barron’s Recursion MC #12
Barron’s 2024 AP CS A prep book on Amazon
This question is identical in the 4th edition all the way through the 2024 edition. (If I missed something, please Contact me and let me know.)
| Barron’s Edition | Page # |
|---|---|
| 2024 | 330 |
| 2022 - 2023 | 330 |
| 9th | 307 |
| 8th | 328 |
| 7th | 312 |
| 6th | 307 |
| 5th | 299 |
| 4th | 353 |
Infinite recursion is not an answer choice, so we can ignore it.
The print statement is in the middle of 2 identical recursive calls. The statement prints n. In the first call, the value of n is 3. Whatever the recursive calls print, they print the same thing. This means that 3 will appear in the middle of the output. Only answers (C) and (E) have 3 in the middle.
There are 2 easy ways to distinguish between (C) and (E).
The identical recursive calls must each print the same thing. In case (C), each recursive call prints 121. In case (E), the first call prints 112 and the second call prints 211. Case (C) is correct.
Alternatively, the calls are each made with n - 1. Since the original value of n is 3, both calls must print 2 in the middle. Only case (C) does this.
Barron’s Recursion MC #10
This question is identical in the 4th edition all the way through the 2024 edition. (If I missed something, please Contact me and let me know.)
| Barron’s Edition | Page # |
|---|---|
| 2024 | 329 |
| 2022 - 2023 | 329 |
| 9th | 306 |
| 8th | 327 |
| 7th | 311 |
| 6th | 306 |
| 5th | 298 |
| 4th | 352 |
Infinite recursion is not an answer choice, so we can ignore it.
The print statement appears after the recursive call and prints s.substring(0, 1) (the first character of s). The last thing the method will ever print is the first charater of s.
The recursive call passes s.substring(1) (everything except the first character of s). The method uses the same approach to print everything but the first character of s. The method is printing the string backwards (answer choice (B)).
Even if the above is not obvious, the other answer choices can be easily eliminated.
- Choice (A) is incorrect because the method prints the first character last.
- Choices (C), (D), and (E) are incorrect because the method prints 1 character each time it is run and removes the character it prints. So it will print all of the characters of
s.
Additional Barron’s Recursion MC
Barron’s Recursion MC questions 13, 19, and 20 are also good examples. The explanations in the back of the Barron’s section (at least in the 2022 - 2023 edition) are good.
2004 AP CS A released MC #28
The College Board used to sell the 2004 AP CS A Released Exam on their website. If you don’t have a copy, skip this example.
If you have a copy, see Question 28 in my 2004 AP CS A Exam MC Explanations.
2009 AP CS A released MC #13
The College Board used to sell the 2009 AP CS A Released Exam on their website. If you don’t have a copy, skip this example.
This question is similar to the 2014 AP CS A CD MC #14.
Inifinite recursion is an answer choice, so we will address it first. The base case is x / 10 == 0 (the opposite of the conditional statement). The recursive call is made with x / 10 (x without its last digit). If we repeatedly remove the last digit of x, we will eventually get 0. The method is not infinitely recursive.
The print statement is at the very bottom of the method, after the recursive call. In the initial call, x has the value 123456. The print statement prints x % 10 (the last digit of x). The last thing the method will ever print is 6, the last digit of the original value of x. This eliminates answer choice (D).
All 3 remaining answer choices print 6 last; however, (A) and (B) each only print 2 digits. If the method removes a digit each time, it will print more than 2 digits from a 6 digit number. The answer must be (C).
More recursion resources
- Recursive method analysis
- Recursive method tracing
- Recursive base conversion exercise
- DeterminantFinder exercise
- Merge sort
Help & comments
Get help from AP CS Tutor Brandon Horn