递归求阶乘引发栈溢出的原因解析及LeetCode #172题代码报错排查

为什么递归求阶乘会栈溢出？ #

当你用递归计算findFactorial(n)时，每一次递归调用都会在调用栈中创建一个新的栈帧——这个栈帧会保存当前函数的局部变量、返回地址等信息。Java的默认调用栈深度是有限的（通常在几千级别，比如默认可能是1024或2048），而当n达到10^{4时，递归深度会达到10}4层，远远超过了栈的承载能力，所以就会抛出StackOverflowError。

举个例子：调用findFactorial(10000)会触发findFactorial(9999)，接着是findFactorial(9998)……直到findFactorial(1)，这中间有9999次连续的递归调用，栈根本装不下这么多栈帧，自然就溢出了。

你的解法还有另一个致命问题：数值溢出 #

除了栈溢出，你的代码还存在整数溢出的问题：Java中int类型的最大值是2^31-1（约21亿），而13!的结果是6227020800，已经超过了int的范围。当n≥13时，findFactorial(n)计算出的结果会是错误的溢出值，后续统计末尾零的逻辑自然也得不到正确结果。

正确的解题思路：统计因子5的个数 #

其实求n!末尾零的个数，不需要计算完整的阶乘结果——我们只需要统计1到n中所有数包含的因子5的总个数。原因很简单：末尾的零来自于10的倍数，而10=2×5，在阶乘中因子2的数量远多于因子5，所以有多少个5的因子，就有多少个末尾零。

需要注意的是，像25（5×5）、125（5×5×5）这类数，会贡献多个5的因子，所以我们需要循环计算：

• 先统计n中能被5整除的数的个数：n/5
• 再统计能被25整除的数的个数（每个贡献第二个5）：n/25
• 接着统计能被125整除的数的个数：n/125
• 以此类推，直到除数大于n为止

修正后的代码 #

class Solution {
    public int trailingZeroes(int n) {
        int count = 0;
        // 循环统计所有5的幂次的因子个数
        while (n > 0) {
            n = n / 5;
            count += n;
        }
        return count;
    }
}

这个解法不仅避免了栈溢出和数值溢出，时间复杂度还只有O(log₅n)，效率极高，完全能处理n=10^4的情况。

内容的提问来源于stack exchange，提问作者SomeoneLearning17