为什么在查找数字的阶乘的递归解决方案中会出现堆栈溢出错误？

Question

Given an integer n, return the number of trailing zeroes in n!

Constraints:

0 <= n <= 10<sup>4</sup>

我的代码找到了n个答案！首先，然后计算尾随零的数量。但是，运行代码抛出堆栈溢出异常，我终究无法弄清楚原因。

这是代码：

class Solution {
    public int trailingZeroes(int n){ 
        int fact = findFactorial(n);   // 120
        int ans = 0;
        
        // how many zeroes does fact have? 
        String ansString = Integer.toString(fact);
    
        // edge - if string is only one character long
        if (ansString.length()==1) {
          return 0;  
        } 
        
        // loop from the end counting the continuous zeroes
        for (int i= ansString.length()-1 ; i > 0; i--){
            Character cha = ansString.charAt(i);
            
            if (cha.equals('0')) {
                ans++;
            }
            else {
                break;
            }
        }
        
        return ans;
    }
    
    public int findFactorial(int n){
        // base case
        if (n==1) return 1;
        
        // reduct towards base case
        else {
            int f = n * findFactorial(n-1);
            return f;
        }
    }

}

Answer 1

在我的机器上使用 JVM 的默认堆栈大小的正确构造的递归实现至少可以达到 9000！（好像是到9119了！）才出现栈溢出。因此，可能明确选择了 10000 限制来触发此问题，因此您会想到非递归实现。

这里我实现了循环和递归。

import java.math.BigInteger;

public class BigFactorial {
    public static void main(String[] args) {
        printResult(120, factorialLoop(120));
        printResult(120, factorialRecursive(120));
    }

    static BigInteger factorialLoop(int n) {
        BigInteger f = BigInteger.ONE;
        for (int i = 2; i <= n; i++) {
            f = f.multiply(BigInteger.valueOf(i));
        }
        return f;
    }
    
     static BigInteger factorialRecursive(int n) {
        if (n == 1)
            return BigInteger.ONE;
        return BigInteger.valueOf(n).multiply(factorialRecursive(n-1));
    }

    static void printResult(int n, BigInteger f) {
        System.out.println(n + "! = " + f);
        String fStr = f.toString();
        int len = fStr.length();
        for (int i = len - 1; i >= 0; i--) {
            if (fStr.charAt(i) != '0') {
                System.out.println("There are " + (len - 1 - i) + " trailing zeros.");
                break;
            }
        }

    }
}

Answer 2

您得到 堆栈溢出错误 的原因是因为您在使用 findFactorial 计算阶乘时使用了递归。将其更改为使用循环而不是递归，如此处所示 Find factorial of large numbers in Java。因此你的方法 findFactorial 变成：

BigInteger findFactorial(int n) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 2; i <= n; i++)
        fact = fact.multiply(BigInteger.valueOf(i));
    return fact;
}

然后在调用 findFactorial 的方法中更改行：

int fact = findFactorial(n);
String ansString = Integer.toString(fact);

至

BigInteger fact = findFactorial(n);
String ansString = BigInteger.toString(fact);

Answer 3

这是使用 for 循环的简单方法，

将 your_number 的值更改为运行此代码之前的任意数字。

public static void main(String[] args) {
            String factorial = findFactorial(new BigInteger("your_number")).toString();
            char[] factorialArray = factorial.toCharArray();
            int numberOfZeros = 0;
    
            for (int i = factorialArray.length - 1; i >= 0; i--) {
                if(factorialArray[i] == '0') {
                    numberOfZeros++;
                }
                else {
                    break;
                }
            }
    
            System.out.println(numberOfZeros);
        }
    
        static BigInteger fact = new BigInteger("1");
    
        static BigInteger findFactorial(BigInteger integer) {
            for (int i = 1; i <= integer.intValueExact(); i++) {
                fact = fact.multiply(BigInteger.valueOf(i));
            }
    
            return fact;
        }

Answer 4

你说：

Given an integer n, return the number of trailing zeroes in n!

Constraints:

0 <= n <= 10⁴

首先，您的解决方案将不起作用，因为 int 不能容纳那么大的数字。您需要使用 BigInteger 如下所示。

下面的递归形式将计算 10⁴! 而没有明显的延迟。

public static BigInteger factorial(int n) {
     if (n == 1 || n == 0) {
         return BigInteger.ONE;
     }
     return factorial(n-1).multiply(BigInteger.valueOf(n));
}
String fact = factorial(1000).toString();
System.out.println(fact.replaceAll("\d+?(0*)$", "").length());

打印

但是您不需要计算阶乘来解决实际问题。考虑以下因素。

1 to N 中所有数字的乘积必须有 10 的约数（即 2 和 5）。 5 出现的次数最少，因此这是您需要关注的地方。尾随零的数量等于 10 divides N 的次数。由于 5 可能会将给定项除以不止一次（例如 25 和 125），因此您还需要更新除数。

int n = 1000; // factorial candidate
int sum = 0;
int k;
for (int d = 5; (k = n/d) > 0; d*=5) {
       sum += k;
}
System.out.printf("%d! has %d trailing zeros", n, sum);

打印

1000! has 249 trailing zeros

这是递归解决方案（虽然效率不高）。

public static int trailingZeros (int n) {
    if (n > 0) {
        return trailingZeros(n/5) + n/5;
    }
    return 0;
}

为什么在查找数字的阶乘的递归解决方案中会出现堆栈溢出错误？

why is there a stack overflow error in a recursive solution to finding the factorials of a number?

java

recursion

stack-overflow

factorial