Complete the Recursive method analysis exercises before reviewing the solutions.
Review the Recursive method analysis exercise solutions with AP CS Tutor Brandon Horn.
Each method below is shown as it was originally written (before the purpose was concealed). The headers above each method match the names of the original exercises.
mystery1 method
public static int countOddDigits(int n)
{
if(n == 0)
return 0;
if(n % 2 == 1)
return 1 + countOddDigits(n / 10);
else
return countOddDigits(n / 10);
}
The method counts and returns the number of odd digits in its parameter n.
The base case is n == 0. The method returns 0 because 0 has 0 odd digits.
In both the if and else, the method is called with n / 10, which is n without its last (least significant, rightmost) digit.
During 1 step, the method checks if n is odd (n % 2 == 1). If n is odd, it adds 1 to the result of the recursive call. If n is not odd (even), it does not add 1. Adding 1 to the result each time something is true means the method is counting something. It adds 1 when the digit is odd (see below), so it is counting the number of odd digits.
A common mistake is thinking that the method adds 1 to each odd digit, making the digit even. The method isn’t adding 1 to n / 10 or n % 10. The method is adding 1 to the result of the recursive call with n / 10.
The conditional statement could be written as:
if((n % 10) % 2 == 1)
The last digit of n is what determines if n is odd.
mystery2 method
public static int countOddDigitsAlt(int n)
{
if(n == 0)
return 0;
int oddDigits = countOddDigitsAlt(n / 10);
if(n % 2 == 1)
oddDigits++;
return oddDigits;
}
The method counts and returns the number of odd digits in its parameter n. This is just mystery1/countOddDigits with a variable used to hold the result of the recursive call. Some students prefer the 2 recursive calls featured in mystery1. Some students prefer storing the result of the recursive call in a variable. Both do the same thing.
mystery3 method
public static int sumEvenDigits(int n)
{
if(n == 0)
return 0;
if(n % 2 == 0)
return n % 10 + sumEvenDigits(n / 10);
else
return sumEvenDigits(n / 10);
}
The method returns the sum of the even digits of its parameter n.
The analysis is nearly identical to mystery1/countOddDigits. The only difference is that on 1 step, the method adds n % 10 (the last digit of n) to the result, instead of adding 1.
mystery4 method
// note: overlapping matches count repeatedly
public static int countMatches(String str, String pattern)
{
if(str.length() < pattern.length())
return 0;
int matches = countMatches(str.substring(1), pattern);
if(str.substring(0, pattern.length()).equals(pattern))
matches++;
return matches;
}
The method counts the number of times p/pattern appears in str.
The base case is if str is shorter than p/pattern, in which case str cannot contain p/pattern. This base case is important because the call to substring assumes that str is at least as long as p/pattern.
The conditional statement checks if the first p.length()/pattern.length() letters of str are p/pattern. In other words, the conditional statement checks if str starts with p/pattern. As with mystery1/countOddDigits, the method either adds 1 or does not depending on the condition, so it is counting.
mystery5 method
public static String replace(String str, String find, String replacement)
{
if(str.length() < find.length())
return str;
if(str.substring(0, find.length()).equals(find))
return replacement + replace(str.substring(find.length()), find, replacement);
else
return str.substring(0, 1) + replace(str.substring(1), find, replacement);
}
The method replaces all occurrences of find with replacement.
The base case and the conditional statement are the same as mystery4/countMatches. If str starts with find, the method is called again with find removed from the beginning of str. replacement is appended to the beginning of result of the call. If str does not start with find, a single character is removed from str (and replaced after the call).
mystery6 methods
public static int countNegatives(int[] arr)
{
return countNegatives(arr, 0);
}
private static int countNegatives(int[] arr, int index)
{
if(index >= arr.length)
return 0;
int count = countNegatives(arr, index + 1);
if(arr[index] < 0)
count++;
return count;
}
The methods count the number of negative values in arr.
mystery7 methods
public static void constrain(int[] arr, int min, int max)
{
constrain(arr, min, max, 0);
}
private static void constrain(int[] arr, int min, int max, int index)
{
if(index >= arr.length)
return;
if(arr[index] < min)
arr[index] = min;
if(arr[index] > max)
arr[index] = max;
constrain(arr, min, max, index + 1);
}
The methods constrain each value in arr to be between min and max, inclusive.
This method should have a precondition that min <= max. It was intentionally omitted to avoid hinting at the solution.
mystery8 methods
public static int[] duplicateAll(int[] arr)
{
int[] newArr = new int[arr.length * 2];
duplicateAll(arr, newArr, 0);
return newArr;
}
private static void duplicateAll(int[] oldArr, int[] newArr, int oldIndex)
{
if(oldIndex >= oldArr.length)
return;
newArr[oldIndex] = oldArr[oldIndex];
newArr[oldArr.length + oldIndex] = oldArr[oldIndex];
duplicateAll(oldArr, newArr, oldIndex + 1);
}
The method returns a new array in which the element in the old array appear twice.
duplicateAll(new int[]{1, 2, 3, 4}) returns [1, 2, 3, 4, 1, 2, 3, 4]