什麼是遞迴？#

遞迴（recursion）：嵌套（nesting）以及嵌套的變奏。

它無所不在：故事中的故事、電影中的電影、畫中之畫、俄羅斯娃娃中的俄羅斯娃娃，甚至括號中的括號註解。本章「遞迴」一詞，與第 3 章談的「遞迴可枚舉集合」雖然有關，但著重點不同。

遞迴定義表面看似循環，實則**永遠用「更簡單的自身」**來定義自身——因此不會陷入無窮迴歸或悖論。

推入、彈出與堆疊#

電腦科學提供了三個基本術語：

• 推入（push）：暫停當前任務、記下進度、開始一個（通常較低層的）新任務
• 彈出（pop）：結束當前層級的任務，回到上一層中斷處
• 堆疊（stack）：一張記錄各層中斷處資訊的表（包含「回返位址」、「變數綁定」）

真實生活的範例：
- 一位忙碌的主管接電話：A 來電 → B 插播（A 入棧）
                       → C 插播（B 入棧）→ C 結束 → 回 B → 回 A
- 廣播新聞：主播 → 駐外記者 → 駐外記者播訪談 → 受訪者播錄音帶
            （層層下嵌通常不超過三層，潛意識能自動追蹤）

「push」、「pop」、「stack」的術語源自自助餐廳的托盤堆：壓下一個托盤、彈出最上面的托盤。

音樂中的堆疊#

音樂的轉調（modulation）也可視為一種推入：

• 每次轉調都把當前的調推入心智堆疊
• 抵達主調（tonic）時感受到的「歸位感」，是彈出堆疊到底層的快感
• 但人類的音樂堆疊很「淺」——通常只記住兩層：真正的主調與當前的偽主調（pseudotonic）

巴赫的《小和諧迷宮》（Little Harmonic Labyrinth）刻意用快速轉調把聽者「迷失」在多層調性中——除非你有絕對音感或像忒修斯有阿里阿德涅的線（樂譜），否則就找不回原調。

巴赫的吉格舞曲（gigue）等 AABB 結構的曲子，巧妙地利用兩次「未結束就跳回」的轉調，創造張力與釋放。

語言中的遞迴#

語法結構天生帶有推入-彈出堆疊。德文「動詞放句末」是極端範例：

傳說中的「心不在焉的教授」會用一整堂課鋪陳一個句子，最後一口氣念出一串動詞，由於聽眾的堆疊早已失序，眾人皆茫然。

母語人士常下意識地違反語法慣例，以避免過深的堆疊。

遞迴轉移網路（RTN）#

**遞迴轉移網路（Recursive Transition Network, RTN）**是描述遞迴語法的視覺工具：

• 一張節點與弧線構成的圖
• 起始節點寫 begin，終止節點寫 end
• 中間節點要嘛是基本動作，要嘛是對另一 RTN 的呼叫

ORNATE NOUN（華麗名詞）
begin → [ARTICLE] → [ADJECTIVE]* → [NOUN] → end

可能產出：
- "the shampoo"
- "a thankless brunch"
- "milk"（跳過 article 與 adjective）
- "big red blue green sneezes"（多次 adjective）

當 RTN 直接或間接呼叫自己時，就出現真正的遞迴。例如 FANCY NOUN 可在內部呼叫 FANCY NOUN，產出：

"the strange bagels that the purple cow without horns gobbled"

觸底（bottoming out）：遞迴定義之所以不會無限迴歸，是因為至少一條路徑不涉及自我呼叫。隨機選擇路徑時，最終必會走到不遞迴的分支。

異層級結構（Heterarchy）#

• 層級結構（hierarchy）：有單一最高層
• 異層級結構（heterarchy）：多個程序互相呼叫成迴圈，沒有單一最高層

這個詞由控制論先驅麥卡洛克（Warren McCulloch）提出。即使是異層級結構，最終也必須能「觸底」，否則程序根本無法執行。

圖形 G 與費波那契#

作者展示了一個無限樹結構「圖形 G」，可以用一個遞迴定義生成。其右側邊緣恰好是費波那契數列（Fibonacci sequence）：

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

遞迴定義：
FIBO(n) = FIBO(n-1) + FIBO(n-2)    for n > 2
FIBO(1) = FIBO(2) = 1

更驚人的是，整個「圖形 G」可用單一函數定義：

G(n) = n - G(G(n-1))    for n > 0
G(0) = 0

把 G(n) 畫在 n 之下，便得到整棵樹。增加巢狀層級會得到「圖形 H」：

H(n) = n - H(H(H(n-1)))    for n > 0

一段混沌數列#

並非所有遞迴定義都產生規律。考慮這個 Q 數列：

Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))    for n > 2
Q(1) = Q(2) = 1

前 17 項：1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, ...

越往後走越無法預測。從非常自然的遞迴定義，能產生極為混沌的行為——這暗示了「充分複雜的遞迴系統，可能強到能跳出任何預設模式」，而這正是智能的某種定義。

兩張驚人的遞迴圖#

作者展示兩個源自他研究的圖：

• INT(x)：一個自身由自身複本嵌套構成的函數圖；無限多複本，越靠近角落越小、越接近平直
• Gplot：作者博士論文的研究——「磁場中晶體的電子能譜」的高度理想化版本。當磁場強度比為有理數 p/q 時，恰好有 q 條能帶；無理數時，能帶退化為一個康托集合

一位不可知論的朋友曾形容 Gplot 是「神的畫像」——作者覺得這描述毫不褻瀆。

物質最底層的遞迴#

物理學中的**重整化（renormalization）**也是遞迴的：

• 假想無交互作用的「裸粒子（bare particle）」實際上不存在
• 一個真實電子持續發射、吸收虛光子；虛光子可衰變為電子-正電子對；後者再湮滅成光子……

費曼圖（Feynman diagram）描繪這些過程，並具有「語法」——只有合乎物理守恆律（能量、電荷等）的圖才允許：

一個物理粒子 = 裸粒子 + 周圍無窮多虛粒子組成的雲，巢狀套疊至任意深度。物理學家透過近似最簡單的數百張費曼圖，已能準確預測 μ 子的 g 因子至小數第九位。

複本與「相同性」#

Gplot 的每一個「自身複本」都經過縮放、扭曲、反射——但仍保持骨架同構。艾雪的版畫〈魚與鱗〉（Fishes and Scales）與〈蝴蝶〉（Butterflies）也表達類似想法：

• 魚的 DNA 確實在每個細胞中編碼了「整條魚」
• 所有蝴蝶之間的「相同性」不是細胞對細胞，而是功能部位對功能部位
• 巴赫或艾雪作品中的「風格」，是在任一片段中都能辨識的「簽名」

程式設計與遞迴：模組、迴圈、程序#

• 迴圈（loop）：重複執行類似指令直到滿足條件
• 有界迴圈（bounded loop）vs. 自由迴圈（free loop）：前者迴圈次數已知，後者可能落入「無窮迴圈」
• 巢狀迴圈（nested loops）：例如要檢驗 1 到 5000 是否為質數，需「迴圈裡的迴圈」
• 副程序（subroutine / procedure）：把一組操作命名為單位，便於呼叫
• 擴增轉移網路（ATN, Augmented Transition Network）：加上參數與條件控制路徑選擇的 RTN，可用於產生合語意的英文句子

西洋棋程式中的遞迴#

評估「最好的一步」需要遞迴定義：

最好的一步 = 走出之後讓對手處境最差的那一步
         = 走出之後對手評估認為「對對手最好」的那一步是最差的那一步

「向前看樹（look-ahead tree）」遞迴展開若干層，最終以非遞迴的「板面評估」觸底（依棋子總值、中心控制力等）。

侯世達定律（Hofstadter’s Law）：事情總是花費比你預期更長的時間——即使你已把侯世達定律考慮進去。

這也是一條遞迴定義，當作章節的小幽默。

遞迴與不可預測性#

回到第 3 章的議題：

• 遞迴可枚舉集合是「由起點集（公理）出發、靠規則一步步增長的雪球」
• Q 數列展示了「定義簡單但行為混沌」的可能性
• 充分複雜的遞迴系統或許強到能跳脫所有預設模式——這可能正是智能的一項定義性特徵
• 若我們設計能修改自己的程式（程式作用於程式），這種「糾纏遞迴（tangled recursion）」或許就是智能的核心

這個觀點將為後續關於人工智慧的章節埋下伏筆。