遞歸求冪

Question

我想寫一個遞歸計算指數的小程序，我有點卡住了。這是一項家庭作業，我們被要求有一個基本案例，當指數是一個奇數，當指數是偶數時。到目前爲止，我有這個：

def quick_power(x,n): 
    if n == 0: 
     return 1 
    elif n % 2 != 0: 
     return x * quick_power(x, n-1) 
    elif n % 2 == 0: 
     return quick_power(quick_power(x, n//2), 2) 

而且我知道n％2 == 0的行不是它應該是。任何幫助表示讚賞。謝謝。

Answer 1

假設我們正在評估quick_power(1234, 2)。評價是這樣的：

1. quick_power(1234, 2)
2. quick_power(quick_power(1234, 1), 2)
3. quick_power(1234 * quick_power(1234, 0), 2)
4. quick_power(1234 * 1, 2)
5. quick_power(1234, 2)

...你可以看到，它最終開始評估回到了起點，所以你最終得到無限遞歸。在沒有給你解決方案的情況下，我建議你思考一下：如果我們有一個常量指數（這裏是2），你有沒有一種方法可以計算出來，而不必遞歸呢？

Answer 2

def quick_power(x,n) 

if n == 0: 
    return 1 
elif n % 2 == 0: 
    return quick_power(x * x, n/2) 
else: 
    return x * quick_power(x * x, (n - 1)/2) 

Answer 3

擴展在什麼上面：

遞歸算法遞歸情況下ANS基地例（其中返回一個明確的結果，而不是另一種遞歸的），你可能知道......

對於在這種情況下，您涵蓋了基本情況n = 0和n = 1。但是從@ icktoofay的回覆中，還有另一個基本案例，n = 2。

所以，你的代碼可以寫成：

def quick_power(x,n): 
    if n == 0: 
     return 1 
    elif n == 1: 
     return x 
    elif n == 2: 
     return x * x 
    elif n % 2 != 0: 
     return x * quick_power(x, n-1) 
    elif n % 2 == 0: 
     return quick_power(x,n//2) * quick_power(x,n//2) 

最後一行應該是通過減少遞歸的最大深度（到log2（n）的遞歸），順便更有效。