遞迴與呼叫堆疊

💡 先搞懂問題

第一次看到下面這種程式，多數人會愣一下：函式 total 的本體裡，竟然又寫著 total(n - 1)。自己呼叫自己，聽起來像兩面對照的鏡子，影像一層套一層沒有盡頭；可是這段程式一執行，馬上印出 10，乾淨俐落。它到底什麼時候停下來？答案 10 又是在哪一行、怎麼算出來的？

def total(n):              # 算 1 加到 n 的總和
    if n == 1:
        return 1
    rest = total(n - 1)     # 函式裡呼叫自己
    return n + rest
print(total(4))             # 印出 10

這種「函式在本體裡呼叫自己」的寫法叫遞迴（recursion）。它背後的想法其實很日常：1 加到 4 有點麻煩，但如果有人先告訴你「1 加到 3 是 6」，你只要再加上自己的 4 就好；而「1 加到 3」又可以拆成「1 加到 2，再加 3」……一直拆到「1 加到 1」，這個小到不用算，答案就是 1。遞迴就是把大問題拆成「自己的一小份」加上「同樣形狀、但小一號的問題」，小一號的問題再交給同一個函式去處理。

要看懂遞迴，關鍵是第 9 課學過的呼叫框（frame）：每呼叫一次函式就開一個新框，放這次呼叫自己的參數和區域變數；函式呼叫函式時，框會一層層疊起來，叫呼叫堆疊（call stack）。遞迴只是「被呼叫的函式剛好是自己」，Python 照樣替每一次呼叫開一個新框，所以 total(4)、total(3)、total(2)、total(1) 會各自有一個 n，互不干擾。

生活比喻：簽書會隊伍裡問「你排第幾個？」

虛構的「北辰書店」辦簽書會，隊伍沿著騎樓排得很長。阿哲排在中間，看不到隊伍最前面，想知道自己排第幾個。他不必跑到前面一個一個數，只要拍拍前面那個人問：「你排第幾個？」前面那位也不知道，就照同樣的方法問他前面的人，然後站著等回答。這樣一路往前問，問到排在最前面的那位讀者，她前面已經沒有人了，不用再問任何人，直接回答：「我是第 1 個。」

接著答案開始往回傳：第 2 位聽到「1」，加 1，回頭告訴後面的人「我第 2 個」；第 3 位聽到「2」，加 1……最後阿哲聽到前面的人說「我第 4 個」，自己就是第 5 個。每個人都只做了兩件小事：往前問一次、聽到答案後加 1 再往後說，整條隊伍卻算出了正確的位置。

這個比喻有三個地方和 Python 不一樣。第一，隊伍裡的人本來就站在那裡；Python 的呼叫框卻是呼叫時才開、回傳後就拿掉，所以「往前問」的階段堆疊越長越高，「往回傳」的階段又一層層縮回去。第二，真實的隊伍一定有排頭；程式裡如果忘了寫終止條件，或是每次呼叫並沒有讓問題變小，Python 就會一直「往前問」下去，直到疊了大約一千層，被迫停下並報錯（原理補完第 4 小節會看到那個錯誤畫面）。第三，隊伍裡是不同的人，程式裡卻是同一個函式被呼叫了好幾次：程式碼只有一份，但每一次呼叫都有自己的框、自己的 n，就像每個人手上都拿著同一張規則卡，卡上寫的「我的位置」各填各的。

🎮 互動實驗室一：呼叫框疊上去，再一層層拿掉

這是上面那張樓梯圖的程式，Python 3.13 真的執行一次、逐步記錄下來的結果。按「下一步」，綠色箭頭是下一個要執行的行，黃色是剛執行完的行，灰色 ⏸ 是「呼叫了函式、正在等它回來」的行。右下方的記憶體圖左邊是名字，每一個方框是一個呼叫框；右邊是物件。請盯著左欄數框的數量：往下呼叫時越疊越多，碰到終止條件後，每回傳一次就少一個。停在 🤔 的地方，先猜再按下一步。

🎮 互動實驗室二：倒數計時，事情是去程做還是回程做？

遞迴函式裡的程式碼，可以寫在「呼叫自己」的前面，也可以寫在後面。寫在前面的，會在往下疊的時候執行；寫在後面的，要等下一層回來、往回拿掉的時候才執行。右上角的選單有三段倒數計時：第一段先印再呼叫，第二段先呼叫再印（只把兩行對調），第三段用 while 迴圈改寫。先猜輸出畫面的順序，再一步一步驗證。

🎮 互動實驗室三：換你當 Python

這次沒有播放器幫你走，由你來決定每一步。最下面那個框是「正在執行」的那一層：先判斷它碰到終止條件了沒有，沒碰到就再疊一個框往下問；碰到了就回傳，接著替上一層算出它該回傳的值。可以選「加總」或「階乘」兩個函式：階乘（factorial）是 1 乘到 n，例如 4 的階乘是 4 × 3 × 2 × 1 = 24，寫法和加總只差一個符號。n 選大一點，看堆疊能疊多高。所有答案都和 Python 3.13 實際執行的結果相同。

📘 原理補完

1. 正式名稱一次對照

看官方文件或別人的教學時，會碰到下面這些名詞。左邊兩欄是正式說法，右邊兩欄對應到這一課的程式和播放器畫面。

「堆疊（stack）」這個詞本身就是「一疊東西」的意思，像一疊盤子：新的盤子只能放在最上面，要拿也只能先拿最上面那個，也就是後放進去的先拿出來。呼叫堆疊正是這樣運作：最後開的框一定最先結束。播放器把新的框畫在下面，所以「最上面」在畫面上是最下面那一個，這只是畫法不同。

2. 寫遞迴的兩個要件

一個遞迴函式能正常結束，一定同時滿足兩件事：有終止條件，而且每一次呼叫自己，參數都更接近終止條件。total(n) 的終止條件是 n == 1，每次呼叫傳的是 n - 1，所以從 4 出發，經過 3、2，一定會碰到 1。兩個條件少了任何一個，函式就會一直呼叫下去（第 4 小節）。

自己寫遞迴時，可以照下面三個問題想，順序很重要：

1. 最小的情況是什麼？答案直接是多少？例如「1 加到 1」就是 1、「空串列的總和」是 0、「空字串反過來」還是空字串。這就是終止條件。
2. 大問題怎麼用「小一號問題的答案」組出來？先假設小一號的答案已經有人算好了（就像阿哲相信前面的人會回答），只想「拿到之後要怎麼補上自己的一份」，例如 n + rest、n * rest。
3. 每次呼叫，參數有沒有往終止條件靠近？n 減 1、串列少一個元素、資料夾往下一層，都算靠近；參數原封不動傳下去，或是會跳過終止條件，就會停不下來。

第二點是遞迴最需要練習的地方：不要試著在腦中把每一層都展開，只要相信「小一號的那一層會給我正確答案」，專心寫好這一層該做的事。展開每一層的工作，交給播放器或除錯器就好。

3. 呼叫堆疊有多高？

每一層呼叫在等下一層回來時，它的框都還留在記憶體裡，所以堆疊的高度就是「同時有幾層還沒結束」。total(4) 碰到終止條件的那一刻，記憶體裡同時有 5 個框：全域加上 4 個 total。total(n) 會疊到 n 層，n 越大疊得越高；這也是遞迴比迴圈多花記憶體的地方。

回傳時則反過來：最下面的框 return 之後立刻被拿掉，回傳值交給它上面那一框，那一框從暫停的第 4 行繼續，把值貼到 rest、算出自己的答案、return、被拿掉……一路往上，直到全域的 answer 拿到 10。回傳值一次只往上傳一層，不會直接從最底層跳回全域；每一層都要親手補上自己的那一份加法。

4. 沒有終止條件：RecursionError

如果把實驗室二「先印再呼叫」的倒數計時拿掉 if n == 0 那一段，函式就只剩「印出 n，再呼叫自己」，沒有任何一條路會停下來。下面是 Python 3.13 實際執行的畫面：數字從 3 一路印到 -995，接著出現錯誤。

def countdown(n):
    print(n)
    countdown(n - 1)
countdown(3)

3
2
1
0
-1
⋮（中間省略 989 行）
-991
-992
-993
-994
-995
Traceback (most recent call last):
  File "/tmp/b0_recur/main.py", line 4, in <module>
    countdown(3)
    ~~~~~~~~~^^^
  File "/tmp/b0_recur/main.py", line 3, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  File "/tmp/b0_recur/main.py", line 3, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  File "/tmp/b0_recur/main.py", line 3, in countdown
    countdown(n - 1)
    ~~~~~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

照第 10 課的方法從最後一行讀起：RecursionError: maximum recursion depth exceeded 的意思是「超過遞迴深度的上限」。Python 預設最多讓呼叫堆疊疊到 1000 層，超過就拋出這個錯誤，免得框無止境地疊下去、把記憶體吃光，讓整個程式甚至 Python 本身當掉。往上看 Traceback：同樣的 line 3, in countdown 只印了三次，接著一行 [Previous line repeated 996 more times]，意思是「上一行又重複了 996 次」，Python 幫你把一模一樣的上千層摺疊起來。數一數：全域 1 層，加上 3 + 996 = 999 層 countdown，剛好 1000 層，這也是為什麼畫面上正好印了 999 個數字。

上限可以用內建模組 sys 的 sys.getrecursionlimit() 查詢、用 sys.setrecursionlimit() 調整（要先 import sys，見 模組與 import 節點）。官方文件特別提醒：調得太高可能讓 Python 直接當掉。初學階段碰到這個錯誤，幾乎都是程式本身的問題，而不是上限太低。

有終止條件，卻永遠碰不到。第二個要件被打破時，畫面一模一樣。下面這段想算「5 + 3 + 1」，每次減 2，終止條件卻寫成 n == 0：n 從 5 變成 3、1、-1、-3……正好跳過 0，永遠不會成立。

def total(n):
    if n == 0:
        return 0
    return n + total(n - 2)
print(total(5))

Traceback (most recent call last):
  File "/tmp/b0_recur/main.py", line 5, in <module>
    print(total(5))
          ~~~~~^^^
  File "/tmp/b0_recur/main.py", line 4, in total
    return n + total(n - 2)
               ~~~~~^^^^^^^
  File "/tmp/b0_recur/main.py", line 4, in total
    return n + total(n - 2)
               ~~~~~^^^^^^^
  File "/tmp/b0_recur/main.py", line 4, in total
    return n + total(n - 2)
               ~~~~~^^^^^^^
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

改法是讓終止條件涵蓋所有可能停下的情況，例如寫成 if n <= 0:。同樣的錯也會發生在「忘了讓參數變小」：把 total(n - 1) 誤寫成 total(n)，每一層拿到的都是同一個 n，錯誤畫面也和上面一樣。

忘了寫 return。這是另一個常見的錯，而且錯誤訊息不是 RecursionError。下面第 4 行算出了 n + total(n - 1)，卻沒有把它 return 出去，函式走到結尾，回傳的是 None（第 9 課）：

def total(n):
    if n == 1:
        return 1
    n + total(n - 1)
print(total(3))

Traceback (most recent call last):
  File "/tmp/b0_recur/main.py", line 5, in <module>
    print(total(3))
          ~~~~~^^^
  File "/tmp/b0_recur/main.py", line 4, in total
    n + total(n - 1)
    ~~^~~~~~~~~~~~~~
TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

仔細看會發現一件有趣的事：Traceback 只有兩層。total(1) 正常回傳 1；total(2) 算出 2 + 1 = 3，但沒有 return，所以交回去的是 None；輪到 total(3) 算 3 + None 時才出錯。錯誤出現在上層，真正漏寫的那一行卻是每一層都有的第 4 行。遞迴函式裡「會回傳結果的路線」，每一條都要寫 return。

5. 遞迴與迴圈可以互相改寫

實驗室二的第三段已經看到：倒數計時用 while 迴圈也寫得出來。事實上，任何遞迴都能改寫成迴圈，反過來也一樣，差別在於「重複的狀態放在哪裡」。迴圈從頭到尾只有一個框，靠同一個名字一直改貼來記住進度；遞迴則是每一層開一個新框，進度記在疊起來的那一疊框裡。下面用階乘對照兩種寫法：

# 同一件事的兩種寫法：5 的階乘 5 × 4 × 3 × 2 × 1
def fact(n):
    if n == 1:                  # 終止條件：1 的階乘就是 1
        return 1
    return n * fact(n - 1)      # 自己的 n 乘上「小一號問題」的答案

def fact_loop(n):
    result = 1
    for k in range(2, n + 1):   # k 依序是 2、3、…、n
        result = result * k     # 同一個呼叫框裡，result 一直改貼
    return result

print(fact(5), fact_loop(5))
print(fact(1), fact_loop(1))

120 120
1 1

像加總、階乘、倒數這種「一條直線往下」的問題，用迴圈其實更直接，也不必擔心疊太深；它們在這一課出現，是因為形狀簡單、最適合用來看清楚呼叫框怎麼疊。Python 本身也不鼓勵用遞迴處理很長的資料，例如把一萬個元素的串列用遞迴一個一個加，一定會撞到 1000 層的上限，這種情況請用迴圈或內建的 sum()。

6. 什麼時候用遞迴比較自然：一層包一層的資料

遞迴真正好用的地方，是資料本身就是「大的裡面有同樣形狀的小的」：資料夾裡有檔案，也有資料夾，裡面的資料夾又可能有資料夾；串列裡有數字，也有串列（第 11 課的巢狀資料）。這種資料，你事先不知道會包幾層，用固定幾層的 for 迴圈很難寫，用遞迴卻很自然：碰到數字（或檔案）就直接處理，碰到串列（或資料夾）就交給同一個函式，裡面還有幾層，由它自己去處理。

下面的播放器就是這棵樹的程式。type(x) == list 用第 3 課的 type() 判斷 x 是不是串列（實務上更常寫成 isinstance(x, list)，意思相同）。這個函式沒有寫成 if …: return 的終止條件，但它其實有：串列裡都是數字時，for 迴圈跑完就 return，不會再呼叫自己；而每次呼叫傳進去的都是更內層、更小的串列，一定會走到底。

同樣的寫法換成資料夾：用字典表示一個資料夾，鍵是檔名，值是檔案大小（KB）或另一個字典（子資料夾）。函式一邊印出樹狀目錄，一邊算出總大小；depth 參數記錄現在在第幾層，每往下一層加 1，用來決定縮排幾格。

# 北辰書店的共用資料夾：資料夾裡還有資料夾（用字典表示，數字是檔案大小 KB）
shared = {
    "報價單.pdf": 120,
    "門市照片": {
        "外觀.jpg": 300,
        "活動": {"簽書會.jpg": 250, "海報.png": 180},
    },
    "說明.txt": 4,
}

def folder_size(folder, depth):
    size = 0
    for name, item in folder.items():
        print("  " * depth + name)                    # 依深度縮排，印出樹狀目錄
        if type(item) == dict:                         # 是資料夾：交給同一個函式處理
            size = size + folder_size(item, depth + 1)
        else:                                          # 是檔案：直接加上大小
            size = size + item
    return size

print("合計", folder_size(shared, 0), "KB")

報價單.pdf
門市照片
  外觀.jpg
  活動
    簽書會.jpg
    海報.png
說明.txt
合計 854 KB

注意輸出的順序：「門市照片」底下的兩層全部印完，才輪到最外層的「說明.txt」。這是因為呼叫 folder_size 處理「門市照片」時，最外層的 for 迴圈停在半路等它回來，就像實驗室一裡停在第 4 行的那幾個框。如果想讓這個資料夾再多包十層，函式一個字都不用改。

7. 以後會在哪裡遇到

自己寫遞迴的機會也許不多，但「一層包一層」的資料在 AI 與資料分析裡到處都是：API 回傳的 JSON 是字典裡有串列、串列裡又有字典，要把它攤平成表格時常會寫一個遞迴函式；決策樹（decision tree）模型本身就是一棵樹，畫出它的規則或解釋一筆預測時，就是從樹根一層層往下走；處理資料夾裡的所有檔案、把整份巢狀資料完整複製一份（第 11 課提過，淺複製只複製外層）也是同樣的形狀。讀到這類程式時，先找終止條件在哪、再看每次呼叫傳進去的東西是不是變小了，就能抓到它怎麼運作。另外，第 10 課讀 Traceback 時那一疊 File，就是出錯當下的呼叫堆疊；遞迴出錯時你會看到同一個函式名稱重複好幾層，現在你知道為什麼了。

✅ 自我檢測

6 題原創的程式閱讀題，每題讀一小段遞迴程式、選出結果。所有答案都用 Python 3.13 實際執行確認過；輸出有好幾行時，選項裡用 ⏎ 表示換行。選完會立即顯示對錯與解析，全部作答後出現總分。目前得分：0 / 6