第七章：遞迴定義 — 動畫敘事
第八集 · Ch.7 遞迴定義
用自己
定義自己
定義自己
字典裡查「遞迴」：見「遞迴」。
這個玩笑背後藏著一個強大的數學工具——
遞迴定義讓我們用有限的文字，
描述無限複雜的結構。
這個玩笑背後藏著一個強大的數學工具——
遞迴定義讓我們用有限的文字，
描述無限複雜的結構。
遞迴定義的兩個部分
遞迴定義（Recursive Definition）
每個遞迴定義都必須有兩個部分：
① 基底情形（Base Case）
直接定義最簡單的情況，不用再遞迴。
例：
② 遞迴情形（Recursive Case）
用更小的情況來定義當前情況。
例：
① 基底情形（Base Case）
直接定義最簡單的情況，不用再遞迴。
例：
F(0) = 0，F(1) = 1② 遞迴情形（Recursive Case）
用更小的情況來定義當前情況。
例：
F(n) = F(n-1) + F(n-2)，其中 n ≥ 2
沒有基底情形 → 永遠遞迴，無法結束。
沒有縮小規模 → 無限循環，定義無效。
沒有縮小規模 → 無限循環，定義無效。
四個經典遞迴定義
階乘 n!
0! = 1
n! = n × (n-1)!
（n ≥ 1）
費波那契數
F(0) = 0
F(1) = 1
F(n) = F(n-1)
+ F(n-2)
集合的子集
pow(∅) = {∅}
pow(S∪{x}) =
pow(S) ∪
{T∪{x} |
T∈pow(S)}
二元樹
基底：空樹
遞迴：
左子樹 T_L
根節點 v
右子樹 T_R
Fibonacci 遞迴樹 — 重複計算問題
5
紅色節點表示重複計算。n 越大，重複越嚴重。
F(8) 的遞迴樹有 67 個節點，但只有 9 個不同的值需要計算。
F(8) 的遞迴樹有 67 個節點，但只有 9 個不同的值需要計算。
結構歸納法
對遞迴定義的結構做歸納，就是結構歸納法。
以二元樹的節點數 ≥ 葉節點數 為例：
以二元樹的節點數 ≥ 葉節點數 為例：
基
基底情形：空樹或只有一個葉節點。
空樹：節點數 0 ≥ 葉節點數 0 ✓
單葉：節點數 1 ≥ 葉節點數 1 ✓
空樹：節點數 0 ≥ 葉節點數 0 ✓
單葉：節點數 1 ≥ 葉節點數 1 ✓
設
歸納假設：左子樹 T_L 和右子樹 T_R 各自滿足性質。
即
即
nodes(T_L) ≥ leaves(T_L) 且 nodes(T_R) ≥ leaves(T_R)
推
遞迴情形：整棵樹 T 由根 + T_L + T_R 組成。
由假設：
nodes(T) = nodes(T_L) + nodes(T_R) + 1leaves(T) = leaves(T_L) + leaves(T_R)由假設：
nodes(T) ≥ leaves(T_L) + leaves(T_R) + 1 > leaves(T) ✓
✓
對所有二元樹，節點數 ≥ 葉節點數。
備忘錄法（Memoization）— 互動
計算過的值存起來，下次直接查表，避免重複計算。
按「下一步」看 F(6) 的計算順序。
按「下一步」看 F(6) 的計算順序。
按「下一步」開始計算 F(6)
觀念測驗
下面哪個遞迴定義是有效的（不會無限循環）？
小結
1 / 8
本頁為動畫敘事版。看完後可前往
完整第七章
進行互動練習（Hilbert Hotel、集合大小比較）。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)