StackOverFlow Error For Problem Number 50 in Leetcode

Question

For the below Input I am getting a StackOverflow error. Can u guys help me with an explanation and how to solve this problem in my code.

 System.out.println(myPow(0.00001,2147483647));  

 public static double myPow(double x, int n) {
         
        return helperPow(x,n,1);
        }


     
     private static double helperPow(double x, int n,double d) {
         if(n == 0) {
             return d;
         }
         
         if(n < 0) {
             return  helperPow(x,++n, d/x);
         }
         
         return helperPow(x, --n, d*x); 
         
     }

score 1 · Accepted Answer · answered Jan 09 '22 at 14:35

Using your current approach, the number of levels of recursion will be equal to n, so it will definitely cause a StackOverflow exception as it requires considerable stack space.

Note that if n is an even number, x^n = (x ^ (n/2)) * (x ^ (n/2)).

If n is an odd number, x^n = (x ^ (n/2)) * (x ^ (n/2)) * x.

So you can reduce the number of levels of recursion to log(n), which will definitely not cause a Stackoverflow exception even if n is large (In your case, n is 2147483647, it will take 31 recursions):

    public double myPow(double x, int n) {
        return n >= 0 ? helperPow(x, n) : 1.0 / helperPow(x, -n);
    }
    public double helperPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double y = helperPow(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }

StackOverFlow Error For Problem Number 50 in Leetcode

1 Answers1