Can someone explain this recursive for me?

Question

I get this code from leetcode.

class Solution(object):
    def myPow(self, x, n):
         if n == 0: 
             return 1
         if n == -1: 
             return 1 / x
         return self.myPow(x * x, n / 2) * ([1, x][n % 2])

This code is used to implement poe(x, n), which means x**n in Python.

I want to know why it can implement pow(x, n).

It looks doesn't make sense...

I understand

if n == 0: 
and
if n == -1:

But the core code:

self.myPow(x * x, n / 2) * ([1, x][n % 2])

is really hard to understand.

BTW, this code only works on Python 2.7. If you want to test on Python 3, you should change

myPow(x*x, n / 2) * ([1, x][n % 2])

to

myPow(x*x, n // 2) * ([1, x][n % 2]) 

Answer 1

The recursive function is to compute power (most probably integer, non negative or -1, power) of a number, as you might have expected (something like x = 2.2 and n = 9).

(And this seems to be written for Python 2.x (due to the n/2 having expected result of integer instead of n//2))

The initial returns are very straight-forward math.

 if n == 0: 
     return 1
 if n == -1: 
     return 1 / x

When the power is 0, then you return 1 and then the power is -1, you return 1/x.

Now the next line consists of two elements:

self.myPow(x * x, n/2)
and
[1, x][n%2]

The first one self.myPow(x * x, n/2) simply means you want to make higher power (not 0 or -1) into half of it by squaring the powered number x

(most probably to speed up the calculation by reducing the number of multiplication needed - imagine if you have case to compute 2^58. By multiplication, you have to multiply the number 58 times. But if you divide it into two every time and solve it recursively, you end up will smaller number of operations).

Example:

x^8 = (x^2)^4 = y^4 #thus you reduce the number of operation you need to perform

Here, you pass x^2 as your next argument in the recursive (that is y) and do it recursively till the power is 0 or -1.

And the next one is you get the modulo of two of the divided power. This is to make up the case for odd case (that is, when the power n is odd).

[1,x][n%2] #is 1 when n is even, is x when n is odd

If n is odd, then by doing n/2, you lose one x in the process. Thus you have to make up by multiplying the self.myPow(x * x, n / 2) with that x. But if your n is not odd (even), you do not lose one x, thus you do not need to multiply the result by x but by 1.

Illustratively:

x^9 = (x^2)^4 * x #take a look the x here

but

x^8 = (x^2)^4 * 1 #take a look the 1 here

Thus, this:

[1, x][n % 2]

is to multiply the previous recursion by either 1 (for even n case) or x (for odd n case) and is equivalent to ternary expression:

1 if n % 2 == 0 else x