有人可以为我解释这个递归吗? [英] Can someone explain this recursive for me?
问题描述
我从 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
这篇关于有人可以为我解释这个递归吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
