有人能爲我解釋這個遞歸嗎？

我從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

有人能爲我解釋這個遞歸嗎？

回答

相關問題