Learning Java Recursion, Ackerman function
Solution 1
You need to make your stack larger:
http://thilinamb.wordpress.com/2008/12/22/how-to-increase-the-java-stack-size/
With larger stack it runs without stackoverflow, but gives 0.
EDIT: Your code is wrong, that is why it gives the error. Try to rewrite the code exactly as the definition says:
//I assume that you check that n and m are non-negative before you run this
if (m == 0) {
return n + 1;
} else if (n == 0) {
return Ack(m - 1, 1);
} else {
return Ack(m - 1, Ack(m, n - 1));
}
PS. Don't blame me for posting source code for homework problems. I believe that the best way to learn programming is by reading and understanding someone else's code.
Solution 2
You've exceeded the maximum recursion depth. That's one of the features of the Ackermann function. :)
If you call it with smaller numbers, like Ack(3,3)
, then it doesn't overflow the stack.
It's possible to increase Java's recursion depth limit, but that's not necessarily a good solution. This may be an exercise in transforming the program so that it doesn't use Java's built-in call stack, but keeps track of each call in a data structure (perhaps a Stack). You can also use memoization, where you record the result of the function call so you don't have to compute the same result over and over.
Solution 3
With a return in front, you don't need 'else'.
if (m == 0) return n + 1;
if (n == 0) return ack (m - 1, 1);
return ack (m - 1, ack (m, n - 1));
Comments
-
Benzle almost 2 years
I'm working on a recursive Ackermann function in Java. I am getting an error at may recursive line, 23.
return Ack(m - 1, Ack(m, n - 1));
Thanks so much if anyone could point out what's wrong.
-Kyle
/*enter code here Ackerman's function, A(m, n) is defined: A(0 , n) = n + 1 for n >= 0 A(m , 0) = A(m – 1 , 1) for m > 0 A(m , n) = A(m – 1 , A(m , n - 1)) for n >= 0 */ public class AckFun { public static int Ack(int m, int n) { if (m == 0) { return 2 * n; } else if (m >= 1) { if (n == 0) { return 0; } else if (n == 1) { return 2; } else { return Ack(m - 1, Ack(m, n - 1)); } } return n; // Not sure what to return here, Eclipse suggested this. } public static void main(String args[]) { System.out.println(Ack(3, 4)); } }
-
Joshua DeWald over 14 yearsWell the reason Eclipse requires the "return n" is because otherwise you'd have a section that doesn't return anything. your method is of the form: if (a) else if (b) ... but if neither a or b is true, then you end up outside of either block.
-
beggs over 14 yearsI like that it's java.lang.StackOverflowError
-
OscarRyz over 14 yearsadditional point, Java's methods names start with lowercase. It should be
public static int ack( int m, in n )
-
-
Benzle over 14 yearsReally, the correct output for (3, 3) is 65536. I thought that for (3, 4) it should be 125. ?
-
Benzle over 14 yearsI think something else may be wrong, I think the answer should be 125 for the values (3, 4), small enough to not need the larger stack treatment (yet).