Ackermann function won't work when m >= 4

Question

I'm writing this program for my computer science class and I don't know why it doesn't work. too be clear, the program works when m <= 3.

I've checked that when m = 4 and n = 1, the result should be 65533 so the variable isn't too small. I've tried using int, long, and double.

public class Recursion {

    public static void main(String[] args) {
        System.out.print(ack(3, 8));
    }

    public static long ack(long m, long n) {
        if (m == 0) {
            return n + 1;
        } else if (m > 0 && n == 0) {
            return ack(m - 1, 1);
        }
        return ack(m - 1, ack(m, n - 1));
    }
}

What result are you getting? Are you seeing a `java.lang.StackOverflowError`? — John Kugelman, Oct 27 '22 at 16:03
First of all can you describe what your code is intended to do? Secondly, describe the cases when the code fails. — Alexander Ivanchenko, Oct 27 '22 at 16:03
"doesn't work" is the worst possible description of a problem — Gyro Gearless, Oct 27 '22 at 16:18

score 0 · Accepted Answer · answered Oct 27 '22 at 16:16

What you are experiencing, is a StackOverflowError. You can read more on what causes them and the default stack size etc. here and here.

In your case, simply increasing the stack size will allow you to run this with the inputs 4, 1. You can achieve this by running your program as follows:

javac Recursion.java
java -Xss8m Recursion.java

The -Xss Flag sets a higher stack size, and you should get the expected output 65533 after a while.

Ackermann function won't work when m >= 4

1 Answers1