Implementing Ackermann Function by Java with BigInteger support

Question

I'm getting StackOverflowError (Exception in thread "main" java.lang.StackOverflowError) for the following code. But the program works fine for m=3, n=3 (or other lower values) but does not work for m=4 and n=2 or 3.

public class AckermannFunction
{
   static BigInteger One = BigInteger.ONE;

   static BigInteger Zero = BigInteger.ZERO;

   static BigInteger ackmnFun(BigInteger m, BigInteger n)
   {
      if (m.equals(Zero))
         return n.add(One);

      if (n.equals(Zero))
         return ackmnFun(m.subtract(One), One);

      return ackmnFun(m.subtract(One), ackmnFun(m, n.subtract(One)));
   }

   public static void main(String[] args)
   {
      BigInteger m = new BigInteger("4");
      BigInteger n = new BigInteger("3");

      System.out.println(ackmnFun(m, n));

   }
}

There are too many recursive calls I understand. Is there any way to get rid of this error?

Thanks.

Answer 1

I've found a solution of my question by myself. I want to share it with you.

Since the Ackermann function calls itself for so many times even for a very low value of m & n, what I did, I added few more terminating condition up to m=3 and n=3 (to minimize recursive calls). And the tricks worked. I found initial values by running the original recursive function and then added all these as terminating condition.

The program finds the Ackermann(4,2) in a few seconds now. The answer is very long containing 19729 decimal digits.

Answer 2

Rather than doing this recursively, you could approach it as a dynamic programming problem, and construct a table of values from the bottom up. Then rather than making recursive calls, you simply reference your table to create the next entry.