** recurPower **我知道了，但我不明白它

Question

好吧，讓我開始說是的這是作業。但我有答案（直到它運作起來）我的問題更多的是「如何」，我有老師多次解釋它（網上課），但我只是沒有得到它，希望有人在這裏更好以我想到的方式解釋事物。

這裏是分配：

寫一個函數recurPower(base, exp)它通過遞歸調用自身來解決同一問題的一個較小的版本，然後通過base結果乘以解決最初的問題計算base**exp。

此功能應取兩個值 - base可以是浮點數或整數; exp將是整數≥0。它應該返回一個數值。您的代碼必須是遞歸的 - 不允許使用**運算符或循環結構。好吧，經過幾次試錯嘗試（我的意思是幾個小時的瘋狂改變）後，我想出了正確的代碼，它解決了正確的答案，但我不明白如何。

下面是代碼：

def recurPower(base, exp): 
''' 
base: int or float. 
exp: int >= 0 

returns: int or float, base^exp 
''' 

if exp <= 0: 
    return 1 


return base * recurPower(base, exp - 1) 

第一件事就是EXP = 0，則返回1部分....我不明白爲什麼事情會回來跟1。二是，如果最後一部分的代碼，如果沒有循環，那麼exp會下降1？

Answer 1

第一個問題是爲什麼exp <= 0返回1

根據定義，用0東西作爲指數是1，那麼，

1^0 => 1 
2^0 => 1 
... 

至於第二部分，這是在遞歸工作。如果我打電話recurPower(2, 6)我會得到一系列調用的，看起來像

recurPower(2, 6) => 
2 * recurPower(2, 5) => 
2 * 2 * recurPower(2, 4) => 
... 
2 * 2 * 2 * 2 * 2 * 2 * 1 

這就是答案。

因此，在英文中，2^6與2 * 2^5完全相同。我們使用這個規則將其分解爲更簡單更簡單的指數。

Answer 2

pow(2, 3) 
= 2 * pow(2, 2) 
= 2 * (2 * pow(2, 1)) 
= 2 * (2 * (2 * (pow 2, 0))) 
= 2 * (2 * (2 * 1))) ; base case: n=0 -> return 1 
= 2 * (2 * 2) 
= 2 * 4 
= 8 

在每次遞歸中，都需要一個基本情況，即遞歸停止的條件，否則它永遠不會結束。在乘法中，基本情況可能返回1，因爲乘以1是中性的，即它不影響以前的計算。

除了基本情況，你有一般情況下，你表達的東西的東西「小」，在這裏：n^x = n * n ^（x-1），直到你達到基本情況時X = 0。