結構歸納法（structural induction）

並非只有數字才有「一個最小的，加上由更小者組成的更大者」這種樣貌。一棵樹是一個節點加上更小的子樹；一個鏈結串列是一個頭加上更小的尾；一個合法的算術運算式，要嘛是一個數字，要嘛是兩個更小的運算式由一個運算子連起來。任何以「基底形狀，加上由更小形狀建出更大形狀的規則」來定義的東西，都能用結構歸納法來推理：對基底形狀證明性質，再證明建構規則保住該性質。

嚴格地說，一個遞迴定義的集合有一些建構子（建出元素的方式）。要證明每個元素都有性質 P，你對每個基底建構子證明 P，再對每個組合建構子假設 P 對其組成部分成立，並證明它對整體成立。以二元樹為例，基底是空樹（或葉子），規則是「一個節點帶有左右子樹」。譬如要對滿二元樹證明「葉子數 = 內部節點數 + 1」：單一葉子有 1 片葉子、0 個內部節點，1 = 0+1；對於連接兩棵分別有 (L1, I1) 與 (L2, I2) 葉子／內部節點之子樹的節點，整體有 L1+L2 片葉子與 I1+I2+1 個內部節點，而 L1+L2 = (I1+1)+(I2+1)… = (I1+I2+1)+1，性質被保住。

結構歸納法其實是對結構的大小（或深度）做強歸納法，所以它健全的理由相同：各組成部分總是嚴格更小，於是遞迴會見底。它是證明關於樹、串列、文法與遞迴資料型別之性質的標準方法，也是表述「遞迴恰好對應資料結構的遞迴程序」其正確性最乾淨的框架。陷阱在於漏掉某個建構子（例如處理了內部節點卻沒處理空樹），那會在證明裡留下一個破洞。