Bisect recursive solution to find pow(x,n)

Question

I am working on an introductory recursive problem:

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]

My Solution with bisect divide

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)        

When run the TestCase

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

Report error:

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.

It stops at n=-1 and found the awkward case

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

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

Revised and it works

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)        

However, upon reading the discussion and other submissions. I found that all other cases prefer the base case n < 0

A clear example:

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

I think it not necessary to change negative n to-n, cos 2**10 == 2**5 * 2** 5 and 2**-10== 2**-5 * 2**-5

Since people prefer base case n < 0 than n == -1, what's the benefits?

Answer 1

for "not necessary to change negative n to-n":
I think it is consideration of performance and precision.

• preformance: integer multiplication is faster than float
• precision: when the number is very small, may cause precision loss.

so we prefer to do pow first, then divide.