0

我收到以下代码的 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));

   }
}

我理解的递归调用太多了。有没有办法摆脱这个错误？

谢谢。

4

2 回答 2

1

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

于 2019-06-12T18:44:28.670 回答
0

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

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

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

于 2019-06-19T17:40:50.487 回答