Can someone explain this recursive for me?
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