Ackermann function won't work when m >= 4-CodePudding

Wikipedia: Ackermann function

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));
    }
}

CodePudding user response：

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.