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

问题描述：

我从 leetcode 得到这个代码.

I get this code from 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.

This code is used to implement poe(x, n), which means x**n in Python.

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

I want to know why it can implement 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 上测试，你应该改变

BTW, this code only works on Python 2.7. If you want to test on Python 3, you should change

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

到

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

答

递归函数是计算幂(最有可能是整数，非负数或-1，幂) 的数字，如您所料(类似于 x = 2.2 和 n = 9).

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).

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

(And this seems to be written for Python 2.x (due to the n/2 having expected result of integer instead of n//2))

最初的 returns 是非常简单的数学运算.

The initial returns are very straight-forward math.

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

当幂为0，则返回1，然后幂为-1，则返回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]

第一个 self.myPow(x * x, n/2) 仅仅意味着你想要获得更高的功率(不是 0 或 -1) 通过平方乘方数 x

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

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

(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).

示例:

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

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

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.

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

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

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

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.

举例说明:

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) 等价于三元表达式:

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

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

相关推荐