Question: 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
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 |
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.
public class Activity8A {
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println(i + "th term (iterative) = " + fIterative(i));
System.out.println(i + "th term (recursive) = " + fRecursive(i));
}
System.out.println(" End of processing.");
}
public static int fIterative(int n) {
int value;
value = 1;
for (int i = 1; i <= n; i++) {
value = 3 * value - i;
}
return value;
}
public static int fRecursive(int n) {
int value;
if (n <= 0) {
value = 1;
} else {
value = 3 * fRecursive(n - 1) - n;
}
return value;
}
}
public class Activity8B {
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);
System.out.println(" End of processing.");
}
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));
System.out.println(" Maximum (recursively): " + findMaximum(array));
}
public static int findMaximumIterative(int[] values) {
int maximum = Integer.MIN_VALUE;
for (int i = 0; i < values.length; i++) {
if (values[i] > maximum) {
maximum = values[i];
}
}
return maximum;
}
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[pos];
}
}
return maximum;
}
public static int findMaximum(int[] values) {
return findMaximumRecursive(values, 0);
}
}
public class Activity8C {
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 iteration " + tests[i] + ": " + maxRepeatIterative(tests[i]));
System.out.println("testing recursion " + tests[i] + ": " + maxRepeat(tests[i]));
System.out.println("counting all repeats " + tests[i] + ": " + maxCount(tests[i]));
}
System.out.println(" End of processing.");
}
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;
}
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;
}
public static int maxRepeat(String s) {
if (s.length() == 0) {
return 0;
} else {
return maxRepeatRecursive(s.substring(1), 1, s.charAt(0));
}
}
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;
}
public static int maxCount(String s) {
if (s.length() == 0) {
return 0;
} else {
return maxCountRecursive(s.substring(1), 1, s.charAt(0));
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help