第七章：遞迴資料型態
在電腦科學中，我們經常處理遞迴定義的資料結構（如列表、樹、表達式）。本章探討如何定義這些型態以及如何對其進行證明。
7.1 遞迴定義與結構歸納法
遞迴定義包含兩部分：
- 基本情況： 定義最簡單的物件。
- 建構規則： 描述如何從已有的物件構造新的物件。
範例：匹配括號字串
定義匹配括號字串的集合 $M$：
1. 基本情況： 空字串 $\lambda \in M$。
2. 建構規則 A： 若 $s \in M$，則 $(s) \in M$。
3. 建構規則 B： 若 $s, t \in M$，則連接字串 $st \in M$。
定義匹配括號字串的集合 $M$：
1. 基本情況： 空字串 $\lambda \in M$。
2. 建構規則 A： 若 $s \in M$，則 $(s) \in M$。
3. 建構規則 B： 若 $s, t \in M$，則連接字串 $st \in M$。
🧪 互動：匹配括號建構器
使用下方的規則按鈕來建構匹配括號字串。觀察右側的語法樹如何隨之生長。
λ (空)
起始：λ
結構歸納法
要證明關於遞迴資料型態的性質 $P(x)$，我們使用結構歸納法：
證明基本情況
證明 $P$ 對基本情況（如空字串）成立。
證明建構步驟
假設 $P(s)$ 和 $P(t)$ 成立（歸納假設）。
證明 $P$ 對應用建構規則後的新物件（如 $(s)$ 或 $st$）也成立。
結論
根據結構歸納法原理，$P(x)$ 對所有該型態的物件 $x$ 皆成立。
7.4 算術表達式
算術表達式也是遞迴資料型態的經典例子：
- 基本情況： 任何數值變數（如 $x, y$）或常數是表達式。
- 建構規則： 若 $E_1$ 和 $E_2$ 是表達式，則 $(E_1 + E_2)$, $(E_1 * E_2)$, $-E_1$ 也是表達式。
這種遞迴結構定義了程式語言中解析器的核心邏輯。
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)