python - 有人可以为我解释这个递归吗？

Question

我从 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)，在Python中表示x**n。

我想知道为什么它可以实现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])

到

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

Answer 1

递归函数是计算一个数字的幂(很可能是整数，非负数或-1，幂)，正如您所期望的(类似于x = 2.2 和 n = 9)。

(这似乎是为 Python 2.x 编写的(由于 n/2 的预期结果为 integer 而不是 n//2))

最初的返回是非常简单的数学运算。

 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 或 -1) 通过平方幂数 x

将其减半

(很可能是为了通过减少所需的乘法次数来加快计算速度 - 想象一下，如果您有计算 2^58 的情况。通过乘法，您必须乘以数字 58 次。但如果每次都分成两份递归求解，最终的操作次数会更少)。

例子:

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

在这里，您传递 x^2 作为递归中的下一个参数(即 y)并递归执行直到幂为 0 或 -1。

下一个是你得到两个除幂的模。这是为了弥补奇数情况(即当幂n为奇数时)。

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

如果 n 是 odd，那么通过执行 n/2，您会在此过程中损失一个 x .因此，您必须通过将 self.myPow(x * x, n/2) 与 x 相乘来弥补。但是如果你的n不是奇数(偶数)，你不会丢失一个x，因此你不需要将结果乘以x但按 1。

举例说明:

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

但是

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

因此，这:

[1, x][n % 2]

是将先前的递归乘以 1(对于偶数 n 情况)或 x(对于奇数 n case) 等价于三元表达式:

1 if n % 2 == 0 else x