java - 堆栈溢出错误

Question

我有这种奇怪的错误。

我正在尝试使用 BigInteger 类实现基本的欧几里得算法，如图所示。当我运行它时，它会抛出 StackoverFlowError，而如果我调试它，它会正确运行并给我正确的答案。

我真的不明白调试和正常运行期间的区别。

      static BigInteger gcd(BigInteger a, BigInteger b) {
        if (a.equals(BigInteger.ZERO)) {
            return b;
        } else if (b.equals(BigInteger.ZERO)) {
            return a;
        }
        BigInteger max = a.max(b);
        BigInteger min = a.min(b);
        return gcd(max.subtract(min), min);
      }

Answer 1

如果您将重复的减法替换为 mod 操作，该算法将需要更少的调用。检查如果 max 非常大而 min 非常小会发生什么。

Answer 2

这不是 GCD 的欧几里得算法。正确的 GCD 算法可以很容易地表述为递归过程，因为实际上迭代次数很少。但是这个错误实现的算法可以运行数百万次迭代，例如，如果'a' 是1,000,000 而'b' 是1，这会导致一百万次递归调用。

（但是，该调用是尾递归调用，因此一个好的 Java 实现实际上会优化堆栈帧。但是，这里似乎不会发生这种情况。尽管由于某些未知原因，调试器版本可以实现尾调用优化，尽管这听起来奇怪的。）

在实际算法中，递归步骤是(a % b, b)而不是(a - b, b)。谷歌搜索“euclid GCD 算法”。