Python实现LeetCode MyPow递归代码触发OverflowError原因及修改差异

问题背景 #

在实现LeetCode第50题MyPow的递归解法时，针对测试用例：

x = 2.00000
n = -2147483648

初始代码触发OverflowError，修改递归逻辑后代码正常运行。

初始递归代码 #

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n > 0:
            return self.recur(x, n)
        else:
            return 1.0 / self.recur(x, -n)

    def recur(self, x: float, n: int) -> float:
        if n == 0:
            return 1.0
        else:
            y = self.recur(x, n // 2) ** 2
            return y if n % 2 == 0 else y * x

错误信息 #

OverflowError: (34, 'Numerical result out of range')
  [Previous line repeated 19 more times]
    y = self.recur(x, n // 2) ** 2
Line 13 in recur (Solution.py)
    y = self.recur(x, n // 2) ** 2
Line 13 in recur (Solution.py)
    y = self.recur(x, n // 2) ** 2
Line 13 in recur (Solution.py)
    return 1.0 / self.recur(x, -n)
Line 7 in myPow (Solution.py)
    ret = Solution().myPow(param_1, param_2)
Line 40 in _driver (Solution.py)
    _driver()
Line 51 in <module> (Solution.py)

修改后的递归代码片段 #

将递归方法中的平方逻辑修改为：

y = self.recur(x, n // 2) 
return y*y if n % 2 == 0 else y *y* x

溢出触发原因 #

测试用例中n=-2147483648，代码会调用recur(x, 2147483648)计算正指数幂。递归过程中指数不断折半，子问题的结果会以指数级增长：当递归到深层时，子问题的结果（如2^(2^20)）会远超双精度浮点数的最大可表示范围（约1.8e308）。

初始写法使用**运算符执行平方操作，当数值超出浮点数范围时，Python会直接抛出OverflowError终止程序；而修改后的写法使用*运算符相乘，Python会将超范围结果转换为inf（无穷大），后续计算1.0/inf会得到合法的0.0，不会触发错误。

两种写法的核心差异 #

1. 运算实现方式不同：
   • 初始写法：先通过**运算符对递归结果做平方，再赋值给y；
   • 修改后写法：先保存递归结果到y，再通过*运算符完成平方（或平方后乘x）的计算。
2. 超范围数值处理逻辑不同：
   • **运算符在处理超出浮点数范围的运算时，会抛出OverflowError；
   • *运算符在同样场景下会返回inf，允许程序继续执行后续合法计算。

内容的提问来源于stack exchange，提问作者Francis Hui