有人能为我解释一下这个递归吗？

我从 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])

这段代码用于实现poe(x, n)， 意思是x**n在Python中。

我想知道为什么它可以实现pow(x, n).

看起来没什么意义...

我明白

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

但核心代码：

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

实在是难以理解。

顺便说一句，此代码仅适用于 Python 2.7。如果你想在Python 3上测试，你应该改变

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

to

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

递归函数是计算能力（很可能是integer，非负或-1，幂）的一个数字，正如你可能已经预料到的（类似于x = 2.2 and n = 9).

（这似乎是为Python 2.x（因为n/2预期结果为integer代替n//2))

最初的returns是非常简单的数学。

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

当电源为0，然后你返回1然后功率是-1，你返回1/x.

现在下一行包含两个元素：

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

第一个self.myPow(x * x, n/2)只是意味着您想要获得更高的功率（而不是0 or -1）通过乘方数的平方变成一半x

（很可能是通过减少所需的乘法次数来加速计算 - 想象一下，如果您有需要计算的情况2^58。通过乘法，您必须将数字相乘58次。但如果每次都将其分成两部分并递归地求解，则最终的操作次数会更少）。

Example:

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

在这里，你通过x^2作为递归中的下一个参数（即y）并递归执行，直到幂为0 or -1.

下一个是你得到除幂的二的模。这是为了弥补odd情况（即当电源n是奇数）。

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

If n is odd，然后通过做n/2，你失去了一个x正在进行中。因此你必须通过乘以self.myPow(x * x, n / 2)接着就，随即x。但如果你的n不是奇数（偶数），你不会失去一个x，因此您不需要将结果乘以x but by 1.

举例来说：

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

因此，这个：

[1, x][n % 2]

是将先前的递归乘以1（对于甚至n情况）或x（对于奇数ncase) 等价于三元表达式：

1 if n % 2 == 0 else x