通过 Java 在 BigInteger 支持下实现 Ackermann 函数

Question

我收到以下代码的 WhosebugError（线程 "main" java.lang.WhosebugError 中的异常）。但是该程序适用于 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

与其递归地执行此操作，不如将其视为一个动态规划问题，并自下而上构造一个 table 值。然后无需进行递归调用，只需引用 table 即可创建下一个条目。

Answer 2

我自己找到了问题的解决方案。我想和你分享。

因为即使 m 和 n 的值非常低，Ackermann 函数也会调用自己很多次，我所做的是，我添加了一些终止条件直到 m=3 和 n=3（以最小化递归调用).这些技巧奏效了。我通过运行原始递归函数找到初始值，然后将所有这些添加为终止条件。

程序现在可以在几秒钟内找到 Ackermann(4,2)。答案很长，包含 19729 个十进制数字。

通过 Java 在 BigInteger 支持下实现 Ackermann 函数

Implementing Ackermann Function by Java with BigInteger support

java

stack-overflow

recursion

ackermann