Exercise #8
Solve one of the following three recursive problems:
1. Ackermann’s function is a recursively-defined function where computing a value requires computation of a simpler case of the function. It is formally defined as a function on two values A(m, n), as follows:
A(m, n) = n + 1 if m = 0
A(m – 1, 1) if m > 0 and n = 0
A(m – 1, A(m, n – 1)) if m > 0 and n > 0
2. Write a Java function to compute Ackermann’s function given m and n. Note: the results get too large to compute with even small values of n and m. Try A(2, 3) = 9 or A(3, 2) = 29.
or
3. Write a recursive method that will calculate and return the range of values in an array. The range is defined as the maximum value in the array minus the minimum value. Hint: you will need a different approach than the solution to problem 2, because you need to calculate both the minimum and maximum values, and a method can have only one return value.
or
4. Write a recursive method that will find whether or not a particular substring occurs inside another (like indexOfexcept with a boolean return value). For example, searching “water” for “ate” returns true, but searching “water” for “war” returns false. Here’s the catch: you can only use the String charAt and length methods . Also, be careful, because if you search “array” for “ra”, the answer is true (don’t get caught up looking only at the first “r”). If you like you can have one recursive method that calls another recursive method.
Your solutions must be completely recursive, and have no loops. If your recursive method requires additional parameters not specified by the problem, write a helper method that will call the recursive method with correct initial parameters. Submit your complete recursive method (and any helper methods required) by the due date specified in the course schedule.
Recursive acrobatics
The problem is to write Java programs that will solve some small problems, first using iteration, then using recursion. These problems will include numeric processing, array processing, and string processing.
Problem 1: Recursively-defined sequences
A recursively-defined sequence is a sequence of numbers where each value is calculated using one or more of the previous values in the sequence. The Fibonacci sequence is one of the most famous examples of a recursively-defined sequence. Here is another: define f(n) as three times the previous value in the sequence minus n. The first few terms of this sequence are (starting at n = 0): 1, 2, 4, 9, 23, 64, 186.
To calculate the nth term in this sequence, we can use iteration.
public static int fIterative(int n) {
int value;
value = 1;
for (int i = 1; i <= n; i++) {
value = 3 * value – i;
}
return value;
}
To see the results, we can run the following main program to print the first ten values in the sequence.
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(i + “th term = ” + fIterative(i));
}
}
To write a recursive method instead, we can rewrite the definition of the values in the sequence more formally, including self-reference: f(n) = 3f(n – 1) – n, and f(0) = 1. This can be translated directly into Java.
public static int fRecursive(int n) {
int value;
if (n <= 0) {
value = 1;
} else {
value = 3 * fRecursive(n – 1) – n;
}
return value;
}
Running the same main program, calling fRecursive instead of fIterative, should produce the same results.
Problem 2: Finding the maximum
Finding th e maximum value in an array of numbers is a simple and common array algorithm. Writing an iterative solution to solve the problem is straightforward.
public static int findMaximumIterative(int[] values) {
int maximum = Integer.MIN_VALUE;
for (int i = 0
COMP 1020
/font>
if (values[i] > maximum) {
maximum = values[i];
}
}
return maximum;
}
The only tricky bit is the use of Integer.MIN_VALUE to initialize the maximum. This constant contains the smallest number that can be stored in an integer variable. It is guaranteed that any value in the array will be no smaller, and gives a reasonable result if the array has no values in it (size 0).
The alternative is to assume that the first value in the array is the maximum and go from there. Unfortunately, this will crash if the array has size 0.
To thoroughly test the method, we can write a main program that initializes a few arrays, and calls the method on each of those arrays.
public static void main(String[] args) {
int[] list1 = { 20,10,50,60,-70,40,30 };
int[] list2 = { 90,10,50,60,70,40 };
int[] list3 = { -20,-10,-50,-60,-70,-40,-30,-5 };
int[] list4 = { -20,-10,-50,-60,-70,-40,-30,-10 };
int[] list5 = { 20 };
int[] list6 = { };
test(list1);
test(list2);
test(list3);
test(list4);
test(list5);
test(list6);
}
public static void test(int[] array) {
System.out.print(“Testing { “);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + ” “);
}
System.out.println(“}”);
System.out.println(” Maximum (iteratively): ” + findMaximumIterative(array));
}
To solve the same problem using recursion, it helps to think about the simplest computational step. A value in an array is the maximum if it is larger than the maximum value in the rest of the array. At each step, compare the current value to the result of finding the maximum of the values after it, recursively. For the base case, an array with nothing left to examine has no maximum value (in our case, Integer.MIN_VALUE). To keep track of where we are in the array, we need to pass along a position that will be increased with each recursive call.
public static int findMaximumRecursive(int[] values, int pos) {
int maximum;
if (pos >= values.length) {
maximum = Integer.MIN_VALUE;
} else {
maximum = findMaximumRecursive(values, pos + 1);
if (values[pos] > maximum) {
maximum = values[i];
}
}
return maximum;
}
A helper method will be used to set up the recursion. It will call the recursive method with an initial position of 0, to start at the beginning of the array.
public static int findMaximum(int[] values) {
return findMaximumRecursive(values, 0);
}
Problem 3:
Given a string that contains consecutive repeated characters, find the length of the longest substring of repeated characters. For example, the string “aaabbbbaaccccd” contains groups of four repeated characters (“bbbb” and “cccc”) so the answer is four.
To solve this problem using iteration, we can keep track of the length of the current repeat substring, and the longest one we’ve encountered so far.
public static int maxRepeatIterative(String s) {
int current;
int longest;
current = 0;
longest = 0;
for (int i = 0; i < s.length(); i++) {
if (i > 0 && s.charAt(i – 1) == s.charAt(i)) {
// repeat
current++;
} else {
// different
current = 1;
}
if (current > longest) {
longest = current;
}
}
return longest;
}
Testing this method will involve calling it several times on a number of different strings. To make it easier to add or change the test cases, we will set it up using an array of strings, and a loop that calls the method for each string in the array. That way, we can add more tests by simply adding more values to the array.
public static void main(String[] args) {
String[] tests = { “”, “aaa”, “ababa”, “aaabbbbaaccccd”, “abbbbbaaaaccccbb”, “cddd” };
for (int i = 0; i < tests.length; i++) {
System.out.println(“testing ” + tests[i] + “: ” + maxRepeatIterative(tests[i]));
}
}
The recursive method is going to use a similar strategy, but in order to keep track of the length of the current substring, it will need to be passed as a parameter. We could also pass a counter, and simply rewrite the loop using recursion, but there is an alternative solution. You can determine the number of repeated characters at the beginning of a processed string by checking if the first character is the same as the previous character, then removing the first character and treating it as the previous. Count the repeats as you go. If the number of repeats so far is greater than the number in the rest of the string, then that is the longest repeated substring.
public static int maxRepeatRecursive(String s, int current, char previous) {
int longest;
if (s.length() == 0) {
longest = 0;
} else {
if (s.charAt(0) == previous) {
current++;
} else {
current = 1;
}
longest = current;
current = maxRepeatRecursive(s.substring(1), current, s.charAt(0));
if (current > longest) {
longest = current;
}
}
return longest;
}
The first time this method is called, we have to set up the parameters with a helper method. Because there is no obvious default value for previous, the helper method will actually process (remove and count) the first character. It will therefore also have to check for the possibility that the incoming string is empty.
public static int maxRepeat(String s) {
if (s.length() == 0) {
return 0;
} else {
return maxRepeatRecursive(s.substring(1), 1, s.charAt(0));
}
}
The reason why we used this strategy instead of simply rewriting the loop using recursion (which would have worked fine) is that it illustrates a more naturally recursive solution. And there is one other advantage. If you wanted to change the problem so that it counts the maximum number of times any character is repeated anywhere in the string (rather than consecutively), the iterative solution would require a complete rewrite: it would either have to use a nested loop or non-nested loops and an array where positions correspond to character values.
These programs are left as an activity for practice.
The naturally recursive solution can do it with only minor changes.
public static int maxCountRecursive(String s, int current, char checking) {
int longest;
if (s.length() == 0) {
longest = 0;
} else {
if (s.charAt(0) == checking) {
current++;
longest = current;
} else {
// new character
longest = maxCountRecursive(s.substring(1), 1, s.charAt(0));
}
current = maxCountRecursive(s.substring(1), current, checking);
if (current > longest) {
longest = current;
}
}
return longest;
}
Adding the second recursive call starts a new count every time we encounter a different character in the string. The old recursive call is modified slightly; it will keep counting the character that it was previously checking. The last parameter was renamed to reflect its altered purpose.
A minor change has a major effect, demonstrating the real magic — and challenge — of recursion.
