python - Can someone explain this recursive for me? -

i code 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 used implement poe(x, n), means x**n in python.

i want know why can implement pow(x, n).

it looks doesn't make sense...

i understand

if n == 0:  , if n == -1: 

but core code:

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

is hard understand.

btw, code works on python 2.7. if want test on python 3, should change

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

to

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

the recursive function compute power (most integer, non negative or -1, power) of number, might have expected (something x = 2.2 , n = 9).

(and seems written python 2.x (due n/2 having expected result of integer instead of n//2))

the initial returns straight-forward math.

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

when power 0, return 1 , power -1, return 1/x.

now next line consists of 2 elements:

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

the first 1 self.mypow(x * x, n/2) means want make higher power (not 0 or -1) half of squaring powered number x

(most speed calculation reducing number of multiplication needed - imagine if have case compute 2^58. multiplication, have multiply number 58 times. if divide 2 every time , solve recursively, end smaller number of operations).

example:

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

here, pass x^2 next argument in recursive (that y) , recursively till power 0 or -1.

and next 1 modulo of 2 of divided power. make case odd case (that is, when power n odd).

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

if n odd, doing n/2, lose 1 x in process. have make multiplying self.mypow(x * x, n / 2) x. if n not odd (even), not lose 1 x, not need multiply result x 1.

illustratively:

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

but

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

thus, this:

[1, x][n % 2] 

is multiply previous recursion either 1 (for n case) or x (for odd n case) , equivalent ternary expression:

1 if n % 2 == 0 else x