Ackermann Function of (4,2)

How efficient is this program? How could I make it more efficient?

package main;

import java.math.BigInteger;

public class Ackermann {

public static void main(String[] args) {
System.out.println(ack(BigInteger.valueOf(4),BigInteger.valueOf(2)));

}

public static BigInteger ack(BigInteger a, BigInteger b) {
BigInteger ans;
else if (b.equals(BigInteger.ZERO)) ans = ack(a.subtract(BigInteger.ONE),BigInteger.valueOf(1));
else ans = ack(a.subtract(BigInteger.ONE), ack(a,b.subtract(BigInteger.ONE)));
return (ans);
}

}

• As far as I remember, ack(4,2) is 2^65533-3. Since the only way that ack() can return a specific value is to recurse that deep, there is no way that a machine will ever execute that algorithm. – Andreas Krey Oct 10 '15 at 19:33

The Ackermann function is not designed to be efficient... ;-) It is designed to be a counter-proof to a theoretical construct.

But, the reality is that the BigInteger is required. The conditions are required.

About the only things I can suggest are:

• use better names
• return-early logic
• the ans variable is unnecessary
• always use braces for conditional blocks.
• BigInteger.ONE is already defined, you have used it in some places already, no need for BigInteger.valueOf(1)
• call it ackermann not ack

I would have:

public static BigInteger ackermann(BigInteger a, BigInteger b) {
if (a.equals(BigInteger.ZERO)) {
}
if (b.equals(BigInteger.ZERO)) {
return ackermann(a.subtract(BigInteger.ONE),BigInteger.ONE);
}
return ackermann(a.subtract(BigInteger.ONE), ackermann(a, b.subtract(BigInteger.ONE)));
}