Python 遞迴練習：基線條件與更小的問題
先寫停止條件，遞迴會容易很多。然後只問一個問題：這個函式可以把什麼樣更小的輸入傳給自己？
先寫基線條件
基線條件是可以立刻回答的輸入。倒計時裡，零是自然的停止點。先單獨測試基線條件，再添加遞迴分支。
def countdown(n):
if n == 0:
return 0
return 1 + countdown(n - 1)
print(countdown(4))可計數的遞迴
縮小輸入
每次呼叫都必須朝基線條件靠近。階乘用 n 乘以 factorial(n - 1)，所以輸入每次都減小。沒有這個減小，函式會永遠呼叫自己。
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))每次輸入都更小
小心分叉
有些問題需要兩次遞迴呼叫。斐波那契使用 fib(n - 1) 和 fib(n - 2)。畫出 n = 5 的呼叫樹，會看到重複的分支；這也是大輸入需要快取的原因。
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([2, 4, 6]))列表越來越短
偵錯遞迴錯誤
如果 Python 拋出 RecursionError，在每次呼叫開頭列印輸入。檢查基線條件是否存在，以及每個分支是否都更接近它。問題本身扁平且重複時，迴圈可能更清楚。
def total(items, depth=0):
print(" " * depth, len(items))
if not items:
return 0
return items[0] + total(items[1:], depth + 1)
print(total([1, 2, 3]))追蹤不斷縮短的輸入
你的練習清單
- 寫遞迴呼叫前，先找出最小輸入。
- 確認每個分支都縮小了輸入。
- 手算一個小例子。
- 遞迴沒有帶來清晰度時，改用迴圈。
常見問題
什麼是基線條件？
函式不用再呼叫自己就能回傳答案的輸入。它負責停止遞迴。
為什麼遞迴函式很慢？
它可能重複計算相同的子問題，樸素斐波那契就是例子。記憶化或迭代版本可以避免重複工作。
所有迴圈都能改寫成遞迴嗎？
理論上可以，但不是所有問題都會更清楚。資料或問題天然巢狀時，再用遞迴。
練習遞迴
12 道題，覆蓋基線條件、階乘、斐波那契、列表遞迴和偵錯。
繼續閱讀：