为什么我遇到 LeetCode 算法 #50 的堆栈溢出错误

Question

对于 LeetCode 算法问题 #50 Pow(x, n)。如果我在递归函数中检查 n 是正数还是负数，为什么会出现堆栈溢出错误？但如果我将检查放在递归函数之外，那么它会接受。 测试用例为1.000 -2147483648

检查递归函数。

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

检查递归函数之外。

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

Answer 1

这是因为你的指数（-2147483648，见评论）溢出：

这段代码

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

打印

-2147483648
-2147483648
true

来自 Java 语言规范：

对于整数值，求反与从零减法相同。 Java 编程语言对整数使用补码表示，并且补码值的范围不对称，因此最大负 int 或 long 的求反会得到相同的最大负数。在这种情况下会发生溢出，但不会引发异常。对于所有整数值 x，-x 等于 (~x)+1。

Answer 2

由于算法的递归性质，在递归函数中检查 n 时遇到堆栈溢出错误。当n是一个很大的负值时，每次递归调用都会将n减1，最终导致堆栈溢出。

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

此更正后的代码在递归函数之外执行检查，并将 n 转换为 long 值，这样可以正确处理 n 的大负值，而不会遇到堆栈溢出错误。