The Ackermann Function and Recursion
I've tried to write the recursive Ackermann function in Java. But I think I've gone very very wrong somewhere! Could anyone take a look, check and maybe point my in the right direction of correcting my code? Thanks!
The issue I have with the code is that after I wrote it, I thought, what if n == 0 and m == 0, there's not an area for this? Would this fall under the if (m == 0) or would it need it's own if-statement?
Is my following solution correct? If I give it there same numbers in different sequence it gives a different result and I'm unsure if this is meant to be the case.
public static int ackermann(int m, int n) {
if (m == 0) {
return n + 1;
} else if ((m > 0) && (n == 0)) {
return ackermann(m-1, n);
} else if ((m > 0) && (n > 0)) {
return ackermann(m-1, ackermann(m,n-1));
} else {
return 0;
}
}
I thought about it some more and I think I've gone even more wrong. If you can't figure out what I've done I gave each if statement an opposite, because I thought if the m and n values are given in a different way the following code will work. It clearly doesn't but could someone try to explain where I've gone wrong?
public static int ackermann(int m, int n) {
if (m == 0) {
return n + 1;
} else if (n == 0) {
return m + 1;
} else if ((m > 0) && (n == 0)) {
return ackermann(m-1, n);
} else if ((n > 0) && (m == 0)) {
return ackermann(n-1, m);
} else if ((m > 0) && (n > 0)) {
return ackermann(m-1, ackermann(m,n-1));
} else if ((n > 0) && (m > 0)) {
return ackermann(n-1, ackermann(n, m-1));
} else {
return 0;
}
}
Answer
This part is wrong:
} else if ((m > 0) && (n == 0)) {
return ackermann(m-1, n);
That should be A(m - 1, 1)