AP Computer Science A Prep, 2024 - Rob Franek 2023
12 Recursion
Part V: Content Review for the AP Computer Science A Exam
RECURSION
The final flow control structure that appears on the AP Exam is called recursion. It is not represented in the free-response questions and appears at least once in the multiple-choice questions (but typically only a few times). This structure has a result similar to a loop, but approaches the task in a different manner.
Stay Up to Date!
For late-breaking information about test dates, exam formats, and any other changes pertaining to AP Comp Sci A, make sure to check the College Board’s website at apstudents.collegeboard.org/courses/ap-computer-science-a
Remember those little wind-up toys you played with when you were little? You know, the plastic teeth or bunny (or whatever) with the little white knob on the side? You would wind the knob over and over, and when you let go, the little teeth would move across the table. The more you wound the knob, the longer the teeth would walk. Since the winding is the same action repeated, it can be considered a loop. The unwinding action, however, differentiates this situation from a while or for loop. When an unwinding or “winding down” occurs as a result of a “winding up,” recursion is lurking in the shadows.
The distinguishing characteristic of a recursive method is a call to the very method itself; this statement is called a recursive call. In order to prevent an infinite loop, the recursive method includes a base case, which signals execution to stop recursing and return to each prior recursive call, finishing the job for each. Let’s use an easy example to illustrate this somewhat confusing topic, and then we’ll spice up the example a bit afterward.
Suppose you have a giant bag of small, multicolored, candy-coated chocolates. As a programmer, you naturally do not want to eat these candies in a haphazard manner; instead, you want to use some sort of algorithm. You decide that you will eat random candies, one at a time, until you reach your favorite color; when your favorite color is reached, you will systematically eat the same colors you ate previously, in backward order.
For example, if you eat red -> blue -> orange -> blue -> green, and green is your base case, you will then eat blue -> orange -> blue -> red and the recursion is complete. Pretty tough to remember, right? Well, a recursive method renders this task a cinch. In pseudocode,
eatCandy (color of current candy)
{
if (current candy color is green)
done eating;
else
eat more candy;
}
Although there is no for or while loop in the code, the recursive call to the method will exhibit a looping quality; unlike our previous loops, however, there is a forward/backward progression, as described above.
Let’s add to this task: tell the user that you’re done eating once you finish. Would adding the following line after the if-else statement accomplish this task?
display “I’m done”;
The way recursion works, the task will be accomplished, although perhaps not according to plan. When the base case is reached, execution of the current method is completed, and then the process continues all the way back to the initial recursive call. Since the “I’m done” message is displayed after, and regardless of, the if-else, it will be displayed each time a recursive iteration completes. The result is the displaying of “I’m done” once for every candy that you ate. Nine candies, nine “I’m done” outputs. It works, but probably not as planned.
1. Consider the following method:
// precondition: x >= 0
public int mystery (int x)
{
if (x == 0)
{
return 0;
}
else
{
return ((x % 10) + mystery(x / 10));
}
}
Which of the following is returned as a result of the call mystery(3543)?
(A) 10
(B) 15
(C) 22
(D) 180
(E) Nothing is returned due to infinite recursion.
Here’s How to Crack It
In the method listed in the question, the base case occurs when x is equal to 0. Because the value that is initially passed to the method is 3543, the base case does not yet apply. See what happens on the line return ((x % 10) + mystery (x / 10)).
The expression within the return statement has two parts (x % 10) and mystery(x / 10). Make sure that you understand what (x % 10) and (x / 10) do. If x is a base 10 integer, x % 10 will return the units digit. For example, 348 % 10 returns 8. If x is an int variable, then x / 10 will remove the units digit. For example, 348 / 10 returns 34.
Take a look at (x % 10). This returns the remainder when x is divided by 10. In this case, x is 3543, so 3543 % 10 is 3.
Now what about (x / 10)? 3543 / 10 is 354; integer division truncates the result.
So you now have mystery(3543) — 3 + mystery(354).
Following the same logic as above, mystery(354) will be (354 % 10) + mystery(354 / 10) or mystery(354) = 4 + mystery(35).
So what is mystery(35)? mystery(35) = (35 % 10) + mystery(35 / 10), or simplified, mystery(35) = 5 + mystery(3).
And mystery(3)? mystery(3) = (3 % 10) + mystery(3 / 10), or simplified, mystery(3) = 3 + mystery(0).
But mystery(0) equals 0 (this is the base case), so
mystery(3) = 3 + 0 = 3
mystery(35) = 5 + 3 = 8
mystery(354) = 4 + 8 = 12
mystery(3543) = 3 + 12 = 15
The correct answer is (B).
RECURSIVELY TRAVERSING ARRAYS
Although it is more common to use a for loop to step through an array, it is also possible to use a recursion. For example, say you have a lineup of football players, each of whom has a numbered helmet. You want to step through the lineup and find the position of the person who has “9” written on his helmet:
A recursive solution for this problem is very easy to implement. You need to look through an array of int values and find the position of a specific value, if it’s there.
First, we’ll need to describe the problem in recursive terms.
· If we’ve looked through every item, then return —1.
· If the current item in the array is a match, return its position.
· Or else, restart the process with the next item in the array.
public int findPosition
(int nums[], int key, int currentIndex)
{
//if we’ve already looked through
//the entire array
if (nums.length <= currentIndex)
return -1;
//if the next item in the array is a match,
//then return it
if (nums[currentIndex] == key)
return currentIndex;
//else, step past the current item in the array,
//and repeat the search on the next item
return findPosition(nums, key, currentIndex + 1);
}
This example is slightly more subtle than the others because we’re carrying information from one recursive call to the next. Specifically, we’re using the currentIndex field to pass information from one recursive call to another. Thus, the first recursive call starts looking at position 0, the next one at position 1, and so on.
Let’s go back to our football-player example. You want to step through a lineup of football players and return the position of the player who has the helmet with “9” written on it. Your code would be of the following form:
int [] players = //represents the football players
int pos = findPosition(players, 9, 0);
Study Break
Congratulations! You just tackled all of your AP Computer Science A content review! Finish up this chapter (review Key Terms, complete the Review Drill, look over Summary bullets); then treat yourself! Take a study break, go for a walk, crank up some music, or eat your favorite snack.
KEY TERMS
recursiosn
recursive call
base case
CHAPTER 12 REVIEW DRILL
Answers to the review questions can be found in Chapter 13.
1.Consider the following recursive method:
public int mystery(int x)
{
if (x == 1)
return 2;
else
return 2 * mystery(x — 1);
}
What value is returned as a result of the call mystery(6)?
(A) 2
(B) 12
(C) 32
(D) 64
(E) 128
2.Consider the following recursive method:
public static int mystery(int x)
{
if (x == 0)
{
return 0;
}
else
{
return (x + mystery(x / 2) + mystery(x / 4));
}
}
What value is returned as a result of a call to mystery(10)?
(A) 10
(B) 12
(C) 20
(D) 22
(E) 35
3.Consider the following nonrecursive method:
//precondition: x >= 0
public static int mystery(int x)
{
int sum = 0;
while(x >= 0)
{
sum += x;
x——;
}
return sum;
}
Which of the following recursive methods are equivalent to the method above?
I. public static int mystery2(int x)
{
if (x == 0)
{
return 0;
}
return (x + mystery2(x — 1));
}
II. public static int mystery3 (int x)
{
if (x == 0)
return 0;
else
return mystery3(x — 1);
}
III. public static int mystery4 (int x)
{
if (x == 1)
{
return 1:
}
return (x + mystery4(x — 1));
}
(A) I only
(B) II only
(C) III only
(D) I and II only
(E) II and III only
4.Consider the following method:
public int mystery(int x, int y)
{
if (x >= 100 || y <= 0)
{
return 1;
}
else
{
return mystery(x + 10, y — 3);
}
}
What value is returned by the call mystery (30, 18)?
(A) 0
(B) 1
(C) 6
(D) 7
(E) Nothing will be returned due to infinite recursion.
5.Consider the following incomplete method:
public int mystery(int x)
{
if (x <= 1)
{
return 1;
}
else
{
return (/ * missing code * /);
}
}
Which of the following could be used to replace / * missing code * / so that the value of mystery(10) is 32?
(A) mystery(x — 1) + mystery(x — 2)
(B) 2 * mystery(x — 2)
(C) 2 * mystery(x — 1)
(D) 4 * mystery(x — 4)
(E) 4 + mystery(x — 1)
Summary
o Recursion is the use of a method to call itself. In order to avoid an infinite loop, any recursive method must have a base case that will cease recursion.
o Recursion can be used for searches, certain mathematical algorithms, or to repeat actions until a desired result is obtained.