Why I got an stack overflow error for LeetCode algorithm #50

Question

For the LeetCode algorithm problem #50 Pow(x, n). Why I got an stack overflow error if I put checking n is positive or negative within the recursive function? But if I put the checking outside the recursive function then it will accept. The test case is 1.000 -2147483648

Checking within the recursive function.

class Solution {
    public double myPow(double x, int n) {
        if (n < 0) {
            x = 1 / x;
            n = -n;
            return myPow(x,n);
        } 

        if (n == 0) {
            return 1.0;
        }
        double half = myPow(x, n / 2);
            if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}

Checking outside the recursive function.

class Solution {
    private double fastPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return fastPow(x, N);
    }
}

This is possibly due to tail-call optimization, where if a function only calls itself once, the compiler might expand it to make it effectively iterative. In the first example myPow is exposed as a public method so cannot be tail-optimized. The code works fine, but the possible range of n is limited by stack space. See this post for an example. — meowgoesthedog
– meowgoesthedog, Commented Feb 14, 2018 at 1:47
For which input values are you getting an unexpected StackOverflowError ? — Erwin Bolwidt
– Erwin Bolwidt, Commented Feb 14, 2018 at 1:58
I'm sorry that I forgot to add the test case. It's 1 -2147483648 — xingtian dong
– xingtian dong, Commented Feb 15, 2018 at 2:37

giorgiga · Accepted Answer · 2018-02-15 02:45:17Z

0

It's because your exponent (-2147483648, see coments) overflows:

This code

System.out.println(  Integer.MIN_VALUE );
System.out.println( -Integer.MIN_VALUE );
System.out.println( Integer.MIN_VALUE == -Integer.MIN_VALUE );

prints

-2147483648
-2147483648
true

From the Java Language Specification:

For integer values, negation is the same as subtraction from zero. The Java programming language uses two's-complement representation for integers, and the range of two's-complement values is not symmetric, so negation of the maximum negative int or long results in that same maximum negative number. Overflow occurs in this case, but no exception is thrown. For all integer values x, -x equals (~x)+1.

answered Feb 15, 2018 at 2:45

giorgiga

1,77812 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

CS-Programming69 · Accepted Answer · 2023-11-28 20:47:06Z

You are encountering a stack overflow error when checking n within the recursive function is due to the recursive nature of the algorithm. When n is a large negative value, each recursive call will decrement n by 1, eventually leading to a stack overflow.

class Solution {
    public double myPow(double x, int n) {
        if (n < 0) {
            x = 1 / x;
            long N = -(long) n; // Convert n to long to handle large negative values
            return myPowHelper(x, N);
        } else {
            return myPowHelper(x, n);
        }
    }

    private double myPowHelper(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = myPowHelper(x, n / 2);
        if (n % 2 == 0) {
            return half * half;
        } else {
            return half * half * x;
        }
    }
}

This corrected code performs the check outside the recursive function and converts n to a long value, where it can handle large negative values of n correctly without encountering a stack overflow error.

Collectives™ on Stack Overflow

Why I got an stack overflow error for LeetCode algorithm #50

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related