求pow（x，n）的对分递归解

Question

我正在研究一个介绍性的递归问题：

Pow(x, n) - LeetCode

Implement pow(x, n), which calculates x raised to the power n (x^n).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2^-2 = 1/2^2 = 1/4 = 0.25

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

我的二分法解

class Solution:
    def myPow(self, x: float, n: int) -> float:
        #base case
        if n == 0: return 1
        #recur case 
        else:
            half = self.myPow(x, n//2) #floor           
            if n % 2 == 0: #even                      
                return half**2
            if n % 2 != 0: #odd
                return x * (half**2)        

当运行测试用例时

    def test_b(self):
        x = 2.0
        n = -2
        answer = 0.25
        check = self.solution.myPow(x, n)
        self.assertEqual(answer, check)

报告错误：

DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
.......
DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
DEBUG x: 2.0, n: -1
Fatal Python error: Cannot recover from stack overflow.

它在n=-1停下来，发现了这个尴尬的案例

In [10]: -1 // 2                                                                                                              
Out[10]: -1

In [11]: -2 // 2                                                                                                              
Out[11]: -1

修改过了，很管用

class Solution:
    def myPow(self, x: float, n: int) -> float:
        """
        Runtime: 36 ms, faster than 99.70%
        Memory Usage: 13.2 MB, less than 5.53%
        """
        #base case
        if n == 0: return 1
        if n == -1: return 1/x
        #recur case 
        else:
            logging.debug(f"x: {x}, n: {n}")            
            half = self.myPow(x, n//2) #floor 

            if n % 2 == 0: #even
                logging.debug(f"even: x: {x}, n: {n}, half:{half}")                            
                return half**2
            if n % 2 != 0: #odd
                logging.debug(f"odd: x: {x}, n: {n}, half:{half}")                            
                return x * (half**2)        

但是，在阅读讨论和其他提交的材料时。我发现所有其他情况都更喜欢基本情况n < 0

一个明显的例子：

class Solution(object):
    def myPow(self, x, n):
        """
        :type x: float
        :type n: int
        :rtype: float
        """
        if n == 0:
            return 1
        if n < 0:
            return 1 /self.myPow(x, -n)
        else:
            partial = self.myPow(x, n//2)
            result = partial * partial
            if n % 2 == 1: #odd
                result *= x
            return result

我认为没有必要把负的n改成-n，cos2**10 == 2**5 * 2** 5 and 2**-10== 2**-5 * 2**-5

既然人们更喜欢基本情况n < 0而不是n == -1，那有什么好处呢？你知道吗

Answer 1

对于"not necessary to change negative n to-n"：
我认为这是对性能和精度的考虑。你知道吗

• 性能：整数乘法比浮点运算快
• 精度：当数值很小时，可能会造成精度损失。你知道吗

所以我们更喜欢先做pow，然后再分。你知道吗