深度探秘

遞迴到底在說什麼

遞迴的核心一句話

遞迴 (recursion) 是一種解決問題的方法：把一個問題拆成越來越小的同類子問題，直到小到可以一眼看出答案（這個「夠小的問題」叫做 base case）。

通常做法是——讓一個函式呼叫它自己。聽起來像繞口令，但它能讓很多原本超難寫的程式變得超優雅。

用「加總一串數字」當例子

假裝你忽然不能用 for 或 while 迴圈了，要怎麼算 [1, 3, 5, 7, 9] 的總和？

數學家會說：加法本來就是「兩個數字相加」。那我們就把整串想成一層層的括號：

(1 + (3 + (5 + (7 + 9))))

最內層 (7 + 9) 不用迴圈就能算。算完往外收：

$$ \begin{aligned} total &= (1 + (3 + (5 + (7 + 9)))) \ &= (1 + (3 + (5 + 16))) \ &= (1 + (3 + 21)) \ &= (1 + 24) = 25 \end{aligned} $$

寫成 Python

用文字描述：一串數字的總和 = 第一個數字 + 「剩下那串」的總和。

def list_sum(num_list):
    if len(num_list) == 1:      # base case：只剩一個就是答案
        return num_list[0]
    else:
        return num_list[0] + list_sum(num_list[1:])  # 呼叫自己

第 2 行是逃生門：list 長度為 1 時答案就是它本身。第 5 行函式呼叫自己，每次都丟一個更短的 list 進去。

生活妙喻

俄羅斯娃娃與傳便當

比喻一：俄羅斯娃娃

打開一個俄羅斯娃娃，裡面是一個更小但長得一樣的娃娃；再打開，又是更小的同款娃娃……直到打開最小那顆——裡面是實心的，打不開了。那顆實心娃娃就是 base case。

處理大娃娃的方法，就是「打開它，然後用同樣方法處理裡面那顆」。這正是遞迴。

比喻二：辦公室傳便當數量

你想知道一整排同事手上總共有幾個便當，但你只看得到前面那一位。於是你問前面的人：「你的便當數，加上你前面所有人的便當總數是多少？」

他不知道前面的總數，於是他又問他前面的人同樣的問題……一路傳到最前面那位（base case）——他前面沒人了，所以他只回報自己手上的便當數。

接著答案像接力一樣一路往後加回來，最後傳回你手上。每個人做的事一模一樣，這就是遞迴的精神。

flowchart TD
    A[加總 1 3 5 7 9] --> B[1 加上 加總 3 5 7 9]
    B --> C[3 加上 加總 5 7 9]
    C --> D[5 加上 加總 7 9]
    D --> E[7 加上 加總 9]
    E --> F[只剩 9 直接回傳 9]

實用超能力

什麼時候該想到遞迴

看到這些徵兆，就想想遞迴

• 問題可以用「它自己的縮小版」來定義（總和、階乘、走訪樹狀資料……）。
• 有一個明顯最簡單、可以直接回答的小狀況（空 list、單一元素、數字 0）。

動手追一遍

用 list_sum([1, 3, 5, 7, 9]) 想像呼叫展開：

list_sum([1,3,5,7,9])
= 1 + list_sum([3,5,7,9])
= 1 + (3 + list_sum([5,7,9]))
= 1 + (3 + (5 + list_sum([7,9])))
= 1 + (3 + (5 + (7 + list_sum([9]))))   ← 碰到 base case，回傳 9

碰到 base case 後，答案再一層層收回來，最後得到 25。

自我檢測

計算 [2, 4, 6, 8, 10] 的總和會做幾次「呼叫自己」（遞迴呼叫）？

提示：5 個元素，最外層那次不算遞迴呼叫，從第 2 層算起到 base case 共 4 次。

深度探秘

所有遞迴都要遵守的三條鐵律

像機器人三定律一樣

作者打趣說：就像艾西莫夫筆下的機器人有三大定律，所有遞迴演算法也必須遵守三條鐵律：

1. 必須有 base case（基本情況） —— 一個可以直接解決、不再呼叫自己的最小狀況。
2. 必須改變狀態並朝 base case 前進 —— 每次呼叫，資料都要往「更接近 base case」的方向變。
3. 必須呼叫自己 —— 這正是遞迴的定義。

對照 list_sum

def list_sum(num_list):
    if len(num_list) == 1:                 # 定律 1：base case
        return num_list[0]
    else:
        return num_list[0] + list_sum(num_list[1:])  # 定律 2 + 3

• 定律 1：list 長度為 1 是 base case。
• 定律 2：num_list[1:] 把 list 變短了一格，朝「長度為 1」邁進。
• 定律 3：函式呼叫了自己。

少了哪一條會出事？

少了 base case 或忘了朝它前進，遞迴就會無限往下呼叫，最終把呼叫堆疊撐爆（Python 會丟出 RecursionError）。

生活妙喻

下樓梯找出口

把遞迴想成下樓梯

你被放在一棟樓的某層，要往下走到一樓出口：

• base case：到了一樓，看到出口——停！（沒有 base case，就像樓梯沒有盡頭，你會永遠往下走。）
• 朝 base case 前進：每次都往下走一層，而不是上下亂跳。如果你一下下樓一下上樓，永遠到不了一樓。
• 呼叫自己：在每一層，你做的事情都一樣——「再往下走一層，重複同樣流程」。

三定律的關係圖

flowchart TD
    A[進入遞迴函式] --> B{是否到達 base case}
    B -- 是 --> C[直接回傳答案 停止]
    B -- 否 --> D[改變狀態 讓資料更接近 base case]
    D --> E[呼叫自己處理更小的問題]
    E --> B

少了「往下走」這個動作（定律 2），就算有一樓出口（定律 1）你也永遠到不了。

實用超能力

用三定律設計階乘

練習：寫一個階乘 fact(n)

階乘定義：$n! = n \times (n-1) \times (n-2) \times \dots \times 1$，而且 $0! = 1$。

按三定律一步步來：

1. base case：題目說 $0! = 1$，所以 n == 0 時直接回傳 1。
2. 朝 base case 前進：每次把 n 變成 n-1，越來越接近 0。
3. 呼叫自己：fact(n) = n * fact(n-1)。

def fact(n):
    if n == 0:        # 定律 1
        return 1
    return n * fact(n - 1)   # 定律 2 + 3

為什麼 base case 是 n == 0 最恰當？

因為定義裡明確給了 $0! = 1$。若寫成 n == 1，那 fact(0) 會錯過 base case 一路往負數遞迴，停不下來。選 n == 0 才能涵蓋所有非負整數。

設計任何遞迴前，先問自己這三句：最小狀況是什麼？每次怎麼縮小？縮小後怎麼呼叫自己？

深度探秘

把數字一位一位拆出來

目標

把一個整數轉成某個進位（2 到 16 進位）的字串。例如 10 轉十進位是 "10"、轉二進位是 "1010"。

三個組成部分

1. 把原本的數字拆成一連串個位數。
2. 用查表把單一位數轉成字元。
3. 把這些字元串接成最終字串。

查表很簡單：準備 convert_string = "0123456789ABCDEF"，要第 9 位就取 convert_string[9]，得到 "9"。小於 base 的數字就是我們的 base case。

用整數除法與餘數來縮小

以 769 轉十進位為例，用整數除法除以 base：

• $769 \div 10 = 76$ 餘 $9$ → 餘數 9 就是最低位
• $76 \div 10 = 7$ 餘 $6$
• $7 < 10$ → 碰到 base case

餘數給我們要記住的位數，商則是更小的數字，朝 base case 前進。

def to_str(n, base):
    convert_string = "0123456789ABCDEF"
    if n < base:                      # base case
        return convert_string[n]
    else:
        return to_str(n // base, base) + convert_string[n % base]

print(to_str(1453, 16))   # 5AD

生活妙喻

找零錢與排隊順序

比喻：兌換零錢

想像你要把一大筆錢換成某種面額。每次你「除以面額」，餘數就是這一輪剛好換不滿一枚的零頭（要記下來），商是還沒換的部分（拿去下一輪繼續換）。一直換到剩下不滿一枚為止——那就是 base case。

關鍵：順序為什麼是對的？

餘數其實是從最低位先算出來的。如果你算出餘數就馬上接到字串前面，順序會顛倒！

程式聰明的地方在於：它先呼叫自己（處理更高位），等遞迴回傳後才接上這一位的餘數。這樣高位的字串會先排好，低位才接在後面，順序自然正確。

這正像疊盤子：先放進去的最後才拿出來。它呼應了堆疊的後進先出。

flowchart TD
    A[轉換 10 到 二進位] --> B[先遞迴 轉換 5]
    B --> C[先遞迴 轉換 2]
    C --> D[先遞迴 轉換 1]
    D --> E[1 小於 2 回傳 字元 1]
    E --> F[回到 2 接上餘數 0 得 10]
    F --> G[回到 5 接上餘數 1 得 101]
    G --> H[回到 10 接上餘數 0 得 1010]

實用超能力

親手追 10 轉二進位

一步步追 to_str(10, 2)

to_str(10, 2)
  10 >= 2 → to_str(5, 2) + convert_string[10 % 2]   ＝ ... + "0"
    to_str(5, 2)
      5 >= 2 → to_str(2, 2) + convert_string[5 % 2]   ＝ ... + "1"
        to_str(2, 2)
          2 >= 2 → to_str(1, 2) + convert_string[2 % 2] ＝ ... + "0"
            to_str(1, 2)
              1 < 2 → 回傳 "1"           ← base case

收回來："1" → "1"+"0"="10" → "10"+"1"="101" → "101"+"0"="1010"。

答案 "1010"，順序完全正確！

為什麼一定要用整數除法 // 而不是 /？

在 Python 3，/ 會得到浮點數（如 10/2 = 5.0），拿去當索引或繼續除會出問題。整數除法 // 才能乾淨地得到「商」。

小結守則

凡是「逐位處理」又怕「順序顛倒」的問題，記得：把要接到後面的東西，延後到遞迴回傳之後再接。

深度探秘

把遞迴改寫成迴圈加堆疊

想法

上一節的進位轉換靠遞迴「先呼叫自己、回傳後才接字元」來保持順序。如果我們不用遞迴，而是自己準備一個堆疊呢？

做法：每算出一個位數的字元，就 push 進堆疊；全部算完後，再一個個 pop 出來串接。因為堆疊是後進先出，最後 push 的高位會最先 pop 出來，順序剛好正確。

from pythonds.basic import Stack

r_stack = Stack()

def to_str(n, base):
    convert_string = "0123456789ABCDEF"
    while n > 0:
        if n < base:
            r_stack.push(convert_string[n])
        else:
            r_stack.push(convert_string[n % base])
        n = n // base
    res = ""
    while not r_stack.is_empty():
        res = res + str(r_stack.pop())
    return res

print(to_str(1453, 16))   # 5AD

觀念重點

這段程式用 while 迴圈取代了遞迴呼叫，用顯式（自己建立）的堆疊取代了遞迴自動使用的呼叫堆疊。結果完全一樣，這透露了一件大事：遞迴和堆疊是一體兩面。

生活妙喻

洗碗疊盤子

比喻：疊盤子

你邊洗碗邊把洗好的盤子往上疊（push）。要收進櫃子時，你只能從最上面那個拿起（pop），所以最後洗好的最先被收。

進位轉換時，最低位最先算出來（最先 push 到堆疊底），最高位最後算出來（push 在最上面）。收的時候從上往下拿，於是高位先出、低位後出——剛好排成正確的閱讀順序。

遞迴版 vs 顯式堆疊版

flowchart TD
    A[逐位算出餘數字元] --> B[每個字元 push 進堆疊]
    B --> C{數字是否還大於 0}
    C -- 是 --> A
    C -- 否 --> D[依序 pop 出來串接]
    D --> E[得到正確順序的字串]

實用超能力

什麼時候改用顯式堆疊

為什麼要知道這件事？

1. 理解遞迴：當你卡在「遞迴怎麼會記得回來要做什麼」時，想像背後有個堆疊在幫你存進度，一切就通了。
2. 避免遞迴過深：有些語言（或很深的遞迴）容易把呼叫堆疊撐爆。改成顯式堆疊用迴圈跑，就能繞過深度限制。
3. 更好掌控：顯式堆疊讓你能隨時檢查、印出堆疊內容，除錯更直覺。

動手對照 to_str(10, 2)

顯式堆疊版逐步 push：

n=10 → push 0，n=5
n=5  → push 1，n=2
n=2  → push 0，n=1
n=1  → push 1，n=0  (迴圈結束)
堆疊（由底到頂）：0, 1, 0, 1
pop 串接：1, 0, 1, 0 → "1010"

和遞迴版的答案 "1010" 完全一致。

記住這句話：遞迴用的是系統的堆疊；顯式堆疊只是把它搬到你自己手上。

深度探秘

每次呼叫函式都配一個 stack frame

函式呼叫時電腦做了什麼

當 Python 呼叫一個函式時，系統會配置一個 stack frame（堆疊框架） 來存放這次呼叫的區域變數。當函式回傳時，回傳值會被留在堆疊頂端，供呼叫它的那一方取用。

這就是遞迴運作的祕密

以 to_str(10, 2) 為例，回傳前的呼叫堆疊大致長這樣（最上面是最新的呼叫）：

[ to_str(1, 2)   區域變數 n=1, base=2 ]   ← 最內層，回傳 "1"
[ to_str(2, 2)   區域變數 n=2, base=2 ]
[ to_str(5, 2)   區域變數 n=5, base=2 ]
[ to_str(10, 2)  區域變數 n=10, base=2 ]  ← 最外層

當 to_str(1, 2) 回傳 "1"，這個回傳值就頂替了 to_str(1, 2) 這個呼叫的位置，被用在 "1" + convert_string[2 % 2] 算出 "10"，再往外傳……

回傳值取代了累加器

在 list 加總的例子裡，你可以把「留在堆疊上的回傳值」想成迴圈版本裡那個累加器變數——只是這次是系統的呼叫堆疊在幫你累積。

生活妙喻

一疊待辦便利貼

比喻：暫停手邊工作去處理新任務

你正在算 to_str(10, 2)，算到一半需要先知道 to_str(5, 2) 的答案。於是你拿一張便利貼寫下「我做到哪、手上的 n 是多少」，貼到桌上那疊的最上面，然後先去處理 5 的問題。

處理 5 時又需要 2 的答案，再貼一張……便利貼越疊越高。直到碰到 base case（1），你終於有了一個確定的答案，於是撕掉最上面那張便利貼，回到上一個被打斷的工作，把剛拿到的答案填進去繼續算。

這疊便利貼就是呼叫堆疊，每張便利貼就是一個 stack frame。

每層有自己的變數範圍

重要的是：雖然一直呼叫同一個函式，但每次呼叫都有自己獨立的便利貼，上面的 n 互不干擾。所以 to_str(10,2) 的 n=10 和 to_str(5,2) 的 n=5 不會打架。

flowchart TD
    A[呼叫 to_str 10] --> B[暫停 push frame n=10]
    B --> C[呼叫 to_str 5 push frame n=5]
    C --> D[呼叫 to_str 2 push frame n=2]
    D --> E[呼叫 to_str 1 push frame n=1]
    E --> F[base case 回傳 字串 1 pop frame]
    F --> G[回到 n=2 用回傳值繼續 pop frame]
    G --> H[回到 n=5 再回到 n=10 完成]

實用超能力

看懂堆疊就能寫好遞迴

為什麼這個畫面這麼重要

書中說：只要把這個堆疊的畫面記在腦中，你就會發現寫正確的遞迴函式容易多了。

當你寫遞迴卡住時，問自己：

1. 每次呼叫，系統會幫我把目前的變數存到一個新 frame——所以不必擔心變數被覆蓋。
2. 回傳值會自動回到上一層——所以我**只要寫好「這一層該做什麼、要回傳什麼」**即可。
3. base case 一回傳，撕便利貼的過程就會自動接力把答案組合回去。

與 RecursionError 的關聯

便利貼疊太高，桌子（記憶體）會垮——這就是遞迴過深時的 RecursionError。每一層 frame 都要佔空間，所以遞迴的「深度」會耗用記憶體。

一個實用心法

寫遞迴時，只專注在單一一層：假設「處理更小問題的那次呼叫已經給了我正確答案」，我只要用它把這一層做完。其餘的交給呼叫堆疊。

深度探秘

用畫圖看見遞迴的展開

為什麼要用畫圖學遞迴

遞迴最難的不是寫，而是在腦中想像它怎麼跑。Python 內建的 turtle（海龜繪圖） 模組可以讓遞迴「畫出來」，親眼看著圖形成形，遞迴的過程就突然變得直覺。

海龜很單純：可以前進、後退、左轉、右轉；尾巴放下時移動會畫線。

遞迴畫螺旋

import turtle

my_turtle = turtle.Turtle()
my_win = turtle.Screen()

def draw_spiral(my_turtle, line_len):
    if line_len > 0:                 # base case：長度 <= 0 就停
        my_turtle.forward(line_len)
        my_turtle.right(90)
        draw_spiral(my_turtle, line_len - 5)   # 用更短的長度呼叫自己

draw_spiral(my_turtle, 100)
my_win.exitonclick()

• base case：line_len <= 0 就停止。
• 朝 base case 前進：每次長度減 5。
• 呼叫自己：用縮短後的長度再畫一段。

碎形 fractal 是什麼

碎形指的是：不管放大多少倍，它都長得一樣。海岸線、雪花、山脈、樹枝都有這種「自相似」特性，天生適合用遞迴描述。

生活妙喻

一棵樹是樹幹加兩棵小樹

用碎形語言描述一棵樹

如果碎形是「各種放大倍率下都一樣」，那對樹來說：一根小樹枝，長得就像一整棵樹的縮小版。

於是我們可以這樣定義樹：

一棵樹 = 一段樹幹，加上往右長的一棵更小的樹，再加上往左長的一棵更小的樹。

這個定義裡又出現了「樹」——典型的遞迴定義！

def tree(branch_len, t):
    if branch_len > 5:          # base case：枝太短就停
        t.forward(branch_len)
        t.right(20)
        tree(branch_len - 15, t)   # 右邊的小樹
        t.left(40)
        tree(branch_len - 15, t)   # 左邊的小樹
        t.right(20)
        t.backward(branch_len)

為什麼右轉 20 又左轉 40

畫完右邊小樹後，海龜需要先抵銷剛剛右轉的 20 度，再額外左轉 20 度去畫左樹——加起來剛好左轉 40 度。最後再 right(20)、backward 退回原點，把海龜還原，好讓上一層繼續。

flowchart TD
    A[畫樹幹 前進 branch_len] --> B[右轉 20 度]
    B --> C[遞迴畫右邊更小的樹]
    C --> D[左轉 40 度]
    D --> E[遞迴畫左邊更小的樹]
    E --> F[右轉 20 度 退回原點]

實用超能力

預測畫圖順序與動手改造

樹是怎麼長出來的？

很多人以為樹會左右對稱地同時長出來，其實不是。因為右邊的遞迴呼叫寫在前面，程式會一路往右邊最深的小枝畫到底，再沿著樹幹往回，把整個右半邊畫完，之後才開始畫左半邊。

這正是遞迴「深度優先」的展開順序——先衝到最深，再一層層回來。

動手改造（書中練習）

試著修改 tree 讓它更像真樹：

• 枝越短，線畫越細（依 branch_len 調 pensize）。
• 枝很短時把顏色改成葉子的綠色。
• 每個分岔的轉角隨機取 15 到 45 度之間，自然界沒那麼對稱。
• 每次縮短的量也隨機，而非固定減 15。

帶走的觀念

凡是「整體由縮小版的自己組成」的圖形或結構（樹、海岸線、雪花），用遞迴描述往往最自然、最簡潔。

深度探秘

一個三岔的遞迴

手繪規則

謝爾賓斯基三角形 (Sierpinski triangle) 是另一個經典碎形。手畫規則很簡單：

1. 先畫一個大三角形。
2. 連接三邊的中點，把它切成四個小三角形。
3. 忽略中間那個，對其餘三個角落的三角形，重複同樣的程序。

你可以一直分下去——只要鉛筆夠尖。

base case：用 degree 控制

既然可以無限分下去，那 base case 是什麼？答案是：我們人為設定要分幾層，這個數字叫做碎形的 degree（階數）。每次遞迴把 degree 減 1，減到 0 就停止。

三路遞迴

def sierpinski(points, degree, my_turtle):
    color_map = ['blue', 'red', 'green', 'white',
                 'yellow', 'violet', 'orange']
    draw_triangle(points, color_map[degree], my_turtle)
    if degree > 0:
        sierpinski([points[0], get_mid(points[0], points[1]),
                    get_mid(points[0], points[2])], degree - 1, my_turtle)
        sierpinski([points[1], get_mid(points[0], points[1]),
                    get_mid(points[1], points[2])], degree - 1, my_turtle)
        sierpinski([points[2], get_mid(points[2], points[1]),
                    get_mid(points[0], points[2])], degree - 1, my_turtle)

注意這裡有三個遞迴呼叫，分別處理三個角落的小三角形。get_mid 算兩端點的中點。

生活妙喻

分形印章與『畫幾層就停』

比喻：會自我複製的印章

想像有個神奇印章，蓋一下會在原三角形的三個角各印出一個縮小一半的同款三角形（中間留白）。如果讓這些小三角形也各自蓋章……會無窮無盡。

所以我們事先約定：「只蓋 degree 層就收手」。degree=0 時印章失效，這就是 base case。

三路遞迴的繪製順序

假設角落順序是左下、上、右下。因為三個遞迴呼叫依序執行，程式會：

1. 先一路鑽到左下角最小的三角形，再回來補滿左下區。
2. 接著處理上方，鑽到最頂端最小三角形再補滿。
3. 最後處理右下。

這又是深度優先：總是先往第一個呼叫鑽到底。

flowchart TD
    A[畫目前三角形 用 degree 對應顏色] --> B{degree 是否大於 0}
    B -- 否 --> C[停止 此層結束]
    B -- 是 --> D[遞迴左下角子三角形 degree 減 1]
    D --> E[遞迴上方子三角形 degree 減 1]
    E --> F[遞迴右下角子三角形 degree 減 1]

為什麼每層顏色不同

程式用 color_map[degree] 取色，所以每一個 degree（每一層）會用不同顏色填滿，讓你一眼看出遞迴的層次。

實用超能力

多重遞迴的思考方式

一個函式裡有多個遞迴呼叫，怎麼想？

別試著在腦中同時追三條線！沿用上一節的心法：假設每個子呼叫都會正確畫好它那塊，你只要確保：

1. 先畫好這一層的大三角形。
2. 把三個角落的座標算對，分別丟給三次遞迴。
3. degree 有遞減（朝 base case 前進）、degree=0 有停（base case）。

其餘交給呼叫堆疊。

為什麼忽略中間那塊

中間的三角形不再遞迴，正是謝爾賓斯基三角形「中空」外觀的來源——遞迴只發生在三個角落。

get_mid 的角色

def get_mid(p1, p2):
    return ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)

它回傳兩端點的中點座標，是把大三角形切成小三角形的關鍵小工具。

帶走的觀念

多重遞迴（一層裡呼叫自己很多次）會讓圖形或計算量呈爆炸式成長。每加一層 degree，三角形數量大約變三倍。

深度探秘

古老傳說裡的遞迴難題

謎題規則

河內塔由法國數學家 Lucas 在 1883 年發明。有三根柱子和一疊由大到小的金盤。目標：把所有盤子從一根柱子搬到另一根，但有兩個限制：

1. 一次只能搬一個盤子。
2. 大盤子絕不能疊在小盤子上面。

傳說有 64 個盤子，僧侶以每秒一步的速度搬完世界就會毀滅。別擔心——搬完 64 個盤子需要 $2^{64} - 1 = 18{,}446{,}744{,}073{,}709{,}551{,}615$ 步，約 5849 億年！

從上往下想

假設要搬 5 個盤子。如果我已經會把上面 4 個搬到中繼柱，那我只要：把最底下那個大盤搬到目標柱，再把那疊 4 個搬過去就好。

但我不會搬 4 個怎麼辦？——那就假設我會搬 3 個……一直問下去，直到搬 1 個盤子——這太簡單了！這就是 base case。

高層次步驟

把高度為 height 的塔，從起點柱搬到目標柱，借助中繼柱：

1. 把上面 height-1 個盤子搬到中繼柱（借助目標柱）。
2. 把剩下那一個（最大）盤子搬到目標柱。
3. 把中繼柱上的 height-1 個盤子搬到目標柱（借助起點柱）。

生活妙喻

搬家時的『先騰出空間』

比喻：搬一疊書

你想把書架最下層那本超大的書搬走，但上面壓著一疊書。你不會一本本煩惱——你會：先把上面那疊書整疊暫放到旁邊的椅子，搬走大書，再把那疊書放回原位。

「把上面那疊搬到別處」這件事本身，又是同一個問題的縮小版（少一本）。這就是河內塔的遞迴。

程式碼

def move_tower(height, from_pole, to_pole, with_pole):
    if height >= 1:
        move_tower(height - 1, from_pole, with_pole, to_pole)  # 步驟 1
        move_disk(from_pole, to_pole)                          # 步驟 2
        move_tower(height - 1, with_pole, to_pole, from_pole)  # 步驟 3

def move_disk(fp, tp):
    print("moving disk from", fp, "to", tp)

注意程式碼幾乎跟英文描述一字不差！關鍵在兩個遞迴呼叫：第一個把上層搬去中繼柱，中間搬最大盤，第二個把上層從中繼柱搬到目標柱。

flowchart TD
    A[搬高度 height 從 起點 到 目標] --> B[遞迴 搬 height 減 1 到 中繼柱]
    B --> C[搬最大盤 從 起點 到 目標]
    C --> D[遞迴 搬 height 減 1 從 中繼柱 到 目標]

base case 的巧妙

當 height 為 0 時，if height >= 1 不成立，函式直接返回什麼都不做。正是這個『什麼都不做就返回』，才讓上一層的 move_disk 得以被執行。

實用超能力

為何不用資料結構追蹤盤子

一個讓人驚訝的問題

看完程式你可能會問：為什麼沒有任何資料結構記錄哪根柱子上有哪些盤子？

如果要手動追蹤，你大概會用三個 Stack（每根柱子一個）。但答案是：Python 透過呼叫堆疊隱式地幫我們提供了所需的堆疊。

每一層遞迴的參數（from、to、with 是哪根柱子）都被存在各自的 stack frame 裡，呼叫堆疊自動幫我們記住「現在這層該從哪搬到哪」。我們不必自己管理盤子位置——遞迴的堆疊本質替我們搞定了。

追蹤三個盤子

move_tower(3, "A", "B", "C") 會印出（A 起點、B 目標、C 中繼）：

moving disk from A to B
moving disk from A to C
moving disk from B to C
moving disk from A to B
moving disk from C to A
moving disk from C to B
moving disk from A to B

剛好 $2^3 - 1 = 7$ 步，最少步數！

帶走的觀念

河內塔展示了遞迴最迷人的一面：程式碼幾乎就是問題本身的直接翻譯，而難以想像的複雜行為，竟由短短幾行優雅地展開。

深度探秘

往四個方向試，撒麵包屑記路

問題

一隻海龜被丟在迷宮中間，要找到出口。迷宮由「方格」組成，每格不是通道就是牆。海龜只能走通道，撞牆就得換方向。

搜尋程序

從目前位置出發，依序嘗試：

1. 先往北走一格，從那裡遞迴重複同樣程序。
2. 北邊不行就往南。
3. 南邊不行就往西。
4. 西邊不行就往東。
5. 四個方向都失敗，代表此路不通，回報失敗。

為什麼需要撒麵包屑

假設往北走，下一步又往北；若北邊是牆，程序會改試往南——但往南剛好走回原來的位置！再從那裡開始又往北……陷入無限迴圈。

所以要記住走過的地方：想像有一袋麵包屑，每到一格就撒一顆。若踏進一格發現已經有麵包屑，就立刻退回去換下一個方向。

四個 base case

1. 撞到牆——此格不能走。
2. 踩到已探索過的格子（有麵包屑）——避免繞圈。
3. 走到迷宮外緣且不是牆——找到出口，成功！
4. 四個方向都試過仍失敗——死路。

生活妙喻

希臘神話的線團與探路

比喻：忒修斯的線團

希臘神話裡，忒修斯走進迷宮殺怪獸，靠一團線記住來路才得以走出。我們的麵包屑就是那團線——標記「這裡來過了」，避免鬼打牆。

回溯：返回就是退一步

最妙的是：回溯（backtracking）只不過是從遞迴函式返回而已。當某個方向走到死路（回傳 False），程式自然返回上一層，換下一個方向再試。你不必寫複雜的「往回走」邏輯——遞迴的返回就幫你做到了。

程式核心

def search_from(maze, row, col):
    maze.update_position(row, col)
    if maze[row][col] == OBSTACLE:   # base case 1 撞牆
        return False
    if maze[row][col] == TRIED:      # base case 2 已走過
        return False
    if maze.is_exit(row, col):       # base case 3 找到出口
        maze.update_position(row, col, PART_OF_PATH)
        return True
    maze.update_position(row, col, TRIED)   # 撒麵包屑
    found = search_from(maze, row-1, col) or \
            search_from(maze, row+1, col) or \
            search_from(maze, row, col-1) or \
            search_from(maze, row, col+1)
    ...
    return found

flowchart TD
    A[到達某格 撒麵包屑] --> B{是牆嗎}
    B -- 是 --> C[回傳 失敗]
    B -- 否 --> D{已走過嗎}
    D -- 是 --> C
    D -- 否 --> E{是出口嗎}
    E -- 是 --> F[回傳 成功]
    E -- 否 --> G[依序試 北 南 西 東]
    G --> A

實用超能力

or 短路與順序的影響

四個方向用 or 串起來的巧思

found = search_from(maze, row-1, col) or \
        search_from(maze, row+1, col) or \
        search_from(maze, row, col-1) or \
        search_from(maze, row, col+1)

這裡用了邏輯短路（short circuit）：or 只要前面有一個是 True 就立刻停止，後面的就不執行。

意思是：如果往北就能走出迷宮（回傳 True），南、西、東這三個遞迴呼叫根本不會被嘗試。只有北失敗了才試南，南失敗才試西……。

改變順序會怎樣

書中建議你動手把四個方向的呼叫對調順序，再看海龜怎麼走。你會發現：路徑變了！因為短路求值會優先深入第一個方向。雖然最後找到的出口可能相同，但探索的過程與路徑取決於嘗試順序。

is_exit 怎麼判斷出口

def is_exit(self, row, col):
    return (row == 0 or row == self.rows_in_maze - 1 or
            col == 0 or col == self.columns_in_maze - 1)

只要走到迷宮的最外緣（第 0 列、最後一列、第 0 行或最後一行）且不是牆，就算找到出口。

帶走的觀念

這個迷宮問題濃縮了遞迴的精華：多方向嘗試 + base case 判斷 + 用返回實現回溯，是日後學「深度優先搜尋」的最佳起點。