HOWTO · Python
Python 中的遞迴乘法
在 Python 中使用遞迴將兩個整數相乘
本頁內容
Python 已經可以用 * 乘以整數,但遞迴實作乘法能幫助我們理解如何把問題拆解成更小的同類問題。以下範例涵蓋重複加法、折半策略,以及使用累加器的變化版本。這些範例適合學習;一般應用程式的程式碼請使用內建運算子。
了解遞迴
遞迴函式會以較小的輸入呼叫自身來解決問題。它需要一個基本情況,在不再呼叫函式的情況下傳回結果;也需要一個遞迴情況,讓問題逐步接近基本情況。每次呼叫都會等待下一層呼叫傳回,之後各層呼叫再依序返回並完成尚未執行的運算。
以重複加法實作乘法時,遞迴情況會將乘數減一,再把被乘數加到傳回的結果上。乘數為零時便會到達基本情況。如果沒有最終能停止呼叫的條件,函式就無法產生結果。
基本遞迴乘法
最直接的做法是在每次呼叫時將第二個輸入減一,然後在各層呼叫返回時加上第一個輸入。
執行以下範例:
本節中的程式碼以及顯示的標籤或輸出仍為英文。
def recursive_multiply(a, b):
if b == 0:
return 0
if b < 0:
return recursive_multiply(-a, -b)
return a + recursive_multiply(a, b - 1)
print(recursive_multiply(5, 3))
對於 b 的每個正數單位,函式都會加上一個 a。當 b 為負數時,同時改變兩個運算元的正負號,就能使用相同的正數累加遞迴,同時維持乘積不變;這也能處理負的被乘數。
每次呼叫都會將 b 減一,直到到達基本情況。接著,各層呼叫會依相反順序返回,每一步都加上 a。這種遞迴關係容易理解,但呼叫次數與乘數的絕對值成正比。因此,乘數很大時可能超過 Python 的遞迴限制。
處理負整數與零
同一個函式可以處理零和所有正負號組合。乘數為零時會立即傳回零。乘數為負數時,同時改變兩個運算元的正負號,就能將運算轉換成正乘數的情況,同時維持數學上的乘積不變。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
def recursive_multiply(a, b):
if b == 0:
return 0
if b < 0:
return recursive_multiply(-a, -b)
return a + recursive_multiply(a, b - 1)
for pair in ((5, 3), (-5, 3), (5, -3), (-5, -3), (5, 0)):
print(pair, recursive_multiply(*pair))
四種正負號組合都會遵循一般的乘積符號規則:兩個運算元同號時結果為正,異號時結果為負。任一運算元為零,結果就是零。迴圈會在每組輸入旁印出乘積,方便比較不同符號組合的結果。
透過折半減少遞迴呼叫
乘數可以折半時,就不必一再減一。對正數 b,令 half 為 a 與 b // 2 的乘積。如果 b 是偶數,完整結果就是 half + half;如果是奇數,則還要再加上一個 a。整數除法與餘數判斷即可表達這個遞迴關係,不需要使用位元運算。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
def multiply_by_halving(a, b):
if b == 0:
return 0
if b < 0:
return multiply_by_halving(-a, -b)
half = multiply_by_halving(a, b // 2)
if b % 2 == 0:
return half + half
return half + half + a
print(multiply_by_halving(5, 3))
每一步遞迴都會大致將乘數折半,因此呼叫深度取決於乘數能被折半的次數,而不是乘數本身的大小。這個方法仍會進行加法,也仍會使用 Python 的呼叫堆疊。它適合用來說明如何縮減遞迴問題;一般程式碼則使用內建乘法會更簡單。
Python 中的尾端遞迴
在尾端遞迴函式中,遞迴呼叫是最後一個運算;累加器會在各層呼叫之間累積結果。這會改變尚未完成的工作記錄位置,但 Python 不會透過重用單一堆疊框架來最佳化尾端呼叫。因此,呼叫堆疊的限制依然存在。
本節中的程式碼以及顯示的標籤或輸出仍為英文。
def tail_recursive_multiply(a, b, accumulator=0):
if b == 0:
return accumulator
if b < 0:
return tail_recursive_multiply(-a, -b, accumulator)
return tail_recursive_multiply(a, b - 1, accumulator + a)
print(tail_recursive_multiply(5, 3))
累加器從零開始,每次正向遞迴步驟都會增加一個 a。乘數到達零時,累加器就保存了乘積。和重複加法一樣,這個版本的呼叫次數與乘數的大小成正比,因此在 Python 中採用尾端呼叫寫法,並不能讓大型輸入變得安全。
遞迴乘法的適用時機
這些實作有助於理解基本情況、遞迴如何逐步推進,以及線性與對數呼叫深度的差別。重複加法和尾端遞迴版本的深度都是線性;折半版本的深度則是對數級。所有版本仍會產生函式呼叫與堆疊成本,而且 Python 並未承諾在不同環境中都有固定的遞迴深度門檻。
實際進行整數運算時,建議使用 a * b:程式碼更清楚,也能避免額外的 Python 層級遞迴呼叫。學習遞迴,或問題明確要求以遞迴方式表達時,再使用遞迴乘法;並確保輸入大小符合所選遞迴方式的限制。