java 中大数的阶乘

Question

我一直在研究这个 recursive function 但找不到自己，这让我找到了 overflow error 并且它一直在出现。我也已经尝试转换为 BigInteger，但没有什么特别的。我在 Eclipse IDE 中没有看到任何警告或语法错误。我必须提交一个有效的大数算法。提前致谢。 :-)

public static BigInteger factorial(int n)
{
    return n > 2 ? new BigInteger(n+"").multiply(factorial(n-1)) : new BigInteger(n+"");
}

Answer 1

问题

您收到错误是因为计算机必须记住您进行的每个方法调用（以及其他信息），直到该方法调用完成，并且 [=32= 上只有这么多 space ] 放在一边记住所有这些。

您递归的次数太多以至于溢出堆栈 space 设置为记住正在进行的方法调用。这就是所谓的堆栈溢出。

可能的解决方案

一个相当有效的算法是使用一个简单的循环。这具有不会导致堆栈溢出的附带好处，因为您不会一遍又一遍地创建更多方法调用，您只需在第一个方法调用中执行操作。

您还应该使用 BigInteger.valueOf(n) 而不是 new BigInteger(n+""):

public static BigInteger factorial(int n) {
    BigInteger result = BigInteger.ONE;
    for (; n > 1; n--) {
        result = result.multiply(BigInteger.valueOf(n));
    }
    return result;
}

这需要我的计算机大约 6 秒来计算 100,000！

更高效的解决方案

还有比这更快的算法。有关详细信息，请参阅 another question 及其链接。