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

I’m solving LeetCode #172:

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

Constraints:

• 0 <= n <= 104

My code finds the answer of n! first and then counts the number of trailing zeroes. However, running the code throws a stack overflow exception, and I can’t for the life of me figure out why.

This is the code:

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

You said:

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

Constraints:

• 0 <= n <= 10⁴

First, your solution won’t work because an int can’t hold that large a number. You need to use BigInteger as shown below.

The following recursive form will compute 10⁴! without much noticeable delay.

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*)$", "$1").length());

prints

249

But you don’t need to compute the factorial to solve the actual problem. Consider the following.

The product of all the numbers from 1 to N must have divisors of 10 (i.e. 2 and 5). 5 will occur the least number of times so that is where you need to focus. The number of trailing zeros is equal to the number of times that 10 divides N. And since 5 may divide a given term more than once (e.g. 25, and 125) you need to update the divisor as well.

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);

prints

1000! has 249 trailing zeros

And here is the recursive solution (although not as efficient).

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