java - 标准阿克曼可以优化吗？

Question

用 Java 编写的标准阿克曼公式:

public static int ack(int x, int y) {

        if (x == 0) {
            return y + 1;
        } else if (y == 0) {
            return ack(x-1, 1); 
        } else {
            // perforce (x > 0) && (y > 0)
            return ack(x-1, ack(x,y-1));
        }
    }

我一直想知道 - 是否有更快的版本来实现这个？我想也许可以通过使用累加器或循环来实现。

Answer 1

是的，例如通过“作弊”。如果m为 5 或更高，则没有任何结果可以用 int 表示。对于 m = 4 ，只有n < 2可以代表案例。对于 m < 4 ，有基于 n 的简单封闭公式.

无论如何，其他一切都会溢出，所以让我们假装这些情况根本没有发生(或者你可能会抛出错误或其他什么)。

未测试:

int Ackerman(int m, int n) {
    switch (m) {
    case 0:
        return n + 1;
    case 1:
        return n + 2;
    case 2:
        return n * 2 + 3;
    case 3:
        return (int)((1L << (n + 3)) - 3);
    case 4:
        return n == 0 ? 13 : 65533;
    }
}