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

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

来源

2016-03-07 Mars Lee

@AnttiHaapala虽然它被标记为'python-2.x'。但是，好的提到。 –

*虽然这是Python 2的标签，因为它假定'/'是地板部门;用''替换'/'，它可以在任何地方使用。 –

你为什么需要一堂课？为什么不只是'def myPow（x，n）'？ – GingerPlusPlus

的递归函数是计算的功率（最有可能整数，非负或-1，功率）数量，正如您可能预期的那样（如x = 2.2和n = 9）。

（这似乎是Python 2.x写入（因的integer代替n//2）的预期已经导致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)只是意味着你要通过平方供电数x

（不 0或 -1）到它的一半，使高功率

（最有可能通过减少所需乘法的数量来加速计算 - 想象一下，如果你有计算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的情况）an d相当于三元表达式：

1 if n % 2 == 0 else x

来源

2016-03-07 06:58:41 Ian

谢谢你的解释！它非常清楚！但为什么这个代码想要使用（x^2）^ 4而不是x^8？ x^8似乎更清楚！ –

@MarsLee我想，很可能通过减少'*'来让速度加快计算过程'（假设'2^50'） – Ian

对不起，我还有一个问题。所以如果n是负数，会发生什么？ –

这是分而治之的技巧。上面的实现是计算幂乘的一种快速方法。在每次调用中，一半的乘法都被消除。

假设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])

来源

2016-03-08 03:21:06

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

回答

相关问题