推薦卡連成一條鏈：A 拉了 B，B 又拉了 C，後面還有。Maya 想知道每條鏈有多深，而不是一個個手數。遞迴在哪裡停下來？
遞迴函式會用更小的輸入呼叫自己。每個遞迴都需要一個能停止呼叫的基線條件，而且每一步都必須朝基線靠近。滿足這兩個條件時，遞迴可以把巢狀問題表達得更短。 你還會追蹤呼叫堆疊、攤平巢狀列表，並快取重複分支。
先寫基線條件
基線條件是不用再呼叫就能回答的最小輸入。factorial(1) 會立刻回傳 1。沒有基線條件，函式會一直呼叫自己，直到 Python 拋出 RecursionError。
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))一次遞迴呼叫
兩次呼叫，更小的輸入
斐波那契天然是兩路遞迴：fib(n) 依賴 fib(n - 1) 和 fib(n - 2)。前兩個值是基線條件。畫出小 n 的呼叫樹，就能看出這個版本為什麼會重複計算。
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))分叉的遞迴
走訪巢狀列表
遞迴列表函式先處理第一個元素，再把剩下的列表交給更小的呼叫。空列表是基線條件。這個模式不只適用於平鋪列表，也適用於樹和巢狀結構。
def total(items):
if not items:
return 0
return items[0] + total(items[1:])
print(total([1, 2, 3]))不斷縮短的列表
呼叫堆疊會反向展開
每次遞迴呼叫都會暫停它的呼叫者。基線條件先回傳，然後每一層呼叫者恢復執行，組合回傳值。向下和向上各列印一次，就能看清最終結果為什麼是從裡往外建構的。
def walk(n):
if n == 0:
print("base")
return 0
print("enter", n)
result = walk(n - 1) + n
print("leave", n, "result", result)
return result
print("total", walk(3))向下進入，向上組合
回傳新結構，不要依賴全局變數
遞迴函式應該回傳自己的部分結果。全局累加器會讓多次呼叫互相干擾，也難以測試。攤平巢狀列表時，把第一個元素的結果和剩餘部分的結果組合起來。
def flatten(items):
if not items:
return []
first, *rest = items
if isinstance(first, list):
return flatten(first) + flatten(rest)
return [first] + flatten(rest)
print(flatten([1, [2, [3, 4]], 5]))組合回傳值，而不是共用狀態
快取重複分支
樸素斐波那契會重複計算相同的子問題。lru_cache 按參數儲存結果，對這種形狀能把指數級工作變成線性級。只有純函式、且參數可雜湊時，快取才是安全的。
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30))
print(fib.cache_info().hits > 0)快取純函式的子問題
本課要點
- 每個遞迴函式都需要基線條件。
- 每次呼叫都必須使用更小或更簡單的輸入。
- 遞迴呼叫回傳的值由呼叫者繼續組合。
- 遞迴太深或重複太多時，迴圈可能更清楚。
- 遞迴從內向外回傳；記憶化能去掉重複分支。
常見錯誤
- 忘記基線條件，導致 RecursionError。
- 用同樣的輸入呼叫函式，而不是縮小輸入。
- 忽略分叉遞迴中的重複計算。
- 快取會讀取變化中的全局狀態或修改輸入的函式。
寫一個遞迴函式，把列表中的數字相加，然後列印 [2, 4, 6] 的結果。
動手試試
改改變數、先預測輸出，再執行程式碼。第一次點擊「執行程式碼」時會下載 Python 執行時，可能需要幾秒鐘。
練習本課
12 道題，作答後立即看到解釋。