Writing recursive methods is not tested on the AP CS A Exam. Although a handful of past free response questions have reasonable recursive solutions, all have non-recursive solutions. The AP CS A Exam does test tracing recursive methods and analyzing recursive methods. It also often features recursive methods with print statements.
Writing recursive methods can help with the above tested material. Recursion is also critical for success in a data structures course, which is the most common next step after AP CS A.
Writing a recursive solution
- Write a base case or base cases. Each base case must be solvable without recursion.
- Assume the method currently being written already works, as long as it is called with something that approaches the base case(s). Make a recursive call or calls.
- Use the result(s) of the recursive call(s) to solve the original problem.
Each of these steps is explained in more detail after the example below.
findLargestEven example
Method findLargestEven is intended to return the largest even digit in num, or -1 if num does not contain an even digit. The precondition is: num >= 0.
public static int findLargestEven(int num)
{
/* to be implemented */
}
Below are example calls to findLargestEven.
findLargestEven(4839); // returns 8
findLargestEven(4); // returns 4
findLargestEven(0); // returns 0
findLargestEven(139); // returns -1
findLargestEven(3); // returns -1
findLargestEven(1); // returns -1
Step 1: Write a base case
A base case is an input, a range of inputs, or a set of inputs that are handled without recursion.
The parameter num is the input. Any single digit value of num (0, 1 … 9) can be handled without recursion. If num is single even digit, num is returned. If num is a single odd digit, -1 is returned.
public static int findLargestEven(int num)
{
if(num < 10)
{
if(num % 2 == 0)
return num;
else
return -1;
}
// More code not yet written
}
For non-negative numbers, num < 10 evaluates to true if and only if num is a single digit. num % 2 == 0 evaluates to true if and only if num is even.
The method now works for any single digit number.
Step 2: Make a recursive call
Assume that the method currently being written (findLargestEven) already works, as long as it is called with something that gets closer to the base case.
Removing a digit gets closer to the base case of a single digit number. num / 10 evalutes to num without the last digit. The call
findLargestEven(num / 10)
returns the largest even digit of num without the last digit, or -1 if num without the last digit has no even digit.
Step 3: Solve the original problem
The original problem is to return the largest even digit in num (or -1). The value returned by the recursive call in Step 2 ignores the last digit. To solve the original problem, consider the last digit.
If the last digit is even and is larger than the largest of the rest of the digits, it is the largest even digit.
public static int findLargestEven(int num)
{
if(num < 10)
{
if(num % 2 == 0)
return num;
else
return -1;
}
int largest = findLargestEven(num / 10);
int lastDigit = num % 10;
if(lastDigit % 2 == 0 && lastDigit > largest)
largest = lastDigit;
return largest;
}
The local variable largest is initialized to the largest value excluding the last digit (the result of the recursive call).
If the last digit is even and is greater than the largest, it is the largest even digit.
The largest even digit is returned.
The expression lastDigit > largest works regardless of whether largest is an actual digit or -1. Any single digit is greater than -1.
More details
Base case(s)
A recursive solution must have a base case, or base cases. A base case is an input, a range of inputs, or a set of inputs that are handled without recursion. A base case does not have to be trival, but it must not be recursive.
Many recursive methods express the base case(s) as conditional statements at the top of the method. This is not a requirement.
To be useful, a base case must meet 2 criteria. It must be possible to handle the base case without recursion. It must be possible to get closer to and eventually hit the base case (or 1 of the base cases if the method has more than 1).
Recursive call(s)
A recursive method makes one or more useful recursive calls. A useful recursive call must work and must provide a result that helps solve the original problem.
For a recursive call to work, it must get closer to (and the sequence of calls must eventually hit) a base case.
For a recursive call to be useful, it must be possible to use the result to help solve the original problem.
When making a recursive call assume that the method currently being written already works, as long as it is called with something that gets closer to the base case. Don’t worry about how the recursive call works (the sequence of resulting calls). Focus on making a useful call.
Solution to original problem
The result(s) of the recursive call(s) from the previous are used to solve the original problem. In some cases, such as recursive binary search, the result of a recursive call is also the solution to the original problem. In other cases, such as in the above example, work must be done to handle whatever the recursive call(s) did not handle.
The focus remains on addressing 1 step of the process, not on stepping into the recursive call(s) or considering the sequence of calls. Considering the sequence of calls is useful for ensuring that a recursive call results in a call sequence that hits a base case. Considering the sequence of calls is not useful for solving the original problem.
Help & comments
Get help from AP CS Tutor Brandon Horn