java - 通过 Java 实现 Ackermann 函数并支持 BigInteger

Question

我收到以下代码的 StackOverflowError (线程“main”java.lang.StackOverflowError 中的异常)。但该程序对于 m=3、n=3(或其他较低值)运行良好，但对于 m=4 和 n=2 或 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));

   }
}

我理解的递归调用太多了。有什么办法可以消除这个错误吗？

谢谢。

Answer 1

您可以将其视为动态规划问题，并自下而上构建值表，而不是递归地执行此操作。然后，您只需引用表来创建下一个条目，而不是进行递归调用。