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

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））

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

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

当幂是0，那么你return1然后幂是-1，你return1/x。

现在下一行由两个元素组成：

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

第一个 self.myPow(x * x, n/2) 只是意味着你想通过对幂数 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情况），等价于三元表达式:

1 if n % 2 == 0 else x

Answer 2

这是分治法。上面的实现是一种快速计算幂的方法。在每次调用时，消除了一半的乘法。

假设n是偶数，x^n可以写成如下（如果n是奇数，需要多乘一次）

x^n = (x^2)^(n/2)
or
x^n = (x^n/2)^2

上面显示的函数实现了第一个版本。第二个也很容易实现（我删除了下面的递归基本情况）

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

Answer 3

正确答案可能在下面

class Solution:
    def myPow(self, x: float, n: int) -> float:

        if n == 0: 
            return 1
        if n > 0:
            return self.myPow(x * x, int(n / 2)) * ([1, x][n % 2])
        else:
            return self.myPow(x * x, int(n / 2)) * ([1, 1/x][n % 2])

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

Can someone explain this recursive for me?

python

recursion

python-2.x