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

Question

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 1

The reason you get a stack overflow error, is because you use recursion when you calculate the factorial with findFactorial. Change it to use a loop instead of recursion, as shown here Find factorial of large numbers in Java. Thus your method findFactorial becomes:

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

Then in your method that calls findFactorial change the lines:

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

to

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

Answer 2

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

Answer 3

Here's a simple way using for loops,

Change the value of your_number to any number before running this code.

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

A properly constructed recursive implementation with the default stack size for the JVM on my machine will work up to at least 9000! (seems to go to 9119!) before there is a stack overflow. So the 10000 limit was probably choose explicitly to trigger this issue so you would think of a non-recursive implementation.

Here I have implemented both a loop and recursion.

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

    }
}