🎯 什麼情境該想到我
當你的遞迴不是拿輸入的某一部分去遞迴，而是自己算出一份全新的資料再遞迴時（快速排序、輾轉相除法、模擬迴圈都是），你就不能再假設它會自己停下來——這時要想到我。
一句話判別（p.226）：
所有自我引用的結構遞迴函式總是使用當前輸入的某個直接部分作為下一步的輸入，對它進一步處理。……因此，如果某個函式的參數是一個普通的表，而且它並不使用表的其餘部分進行遞迴，那麼這個函式定義就不是結構遞迴的，而是生成遞迴的。
書把這種函式直接叫做演算法：「這種形式的遞迴與數學一樣古老，也被稱為演算法。」（p.216）
⚙️ 怎麼用
為什麼需要多一步
結構遞迴之所以安全，是因為它是「順著資料結構走」的（p.223）：
依據訣竅的本質，每個自然遞迴都直接使用輸入中的某個部分，而不是整個輸入。因為資料是以層次的形式構造的，這意味著在遞迴的每一個階段，輸入都會縮短。因此函式遲早會讀入一個不可分割的資料，從而停止。
生成遞迴沒有這個保證：「內部的遞迴不再讀入輸入的某個直接部分，而是某種新的、由輸入生成的資料。」（p.223）書給的反例是把 quick-sort 的分割條件從「嚴格小於」誤寫成「小於等於」，於是單元素輸入會生成跟原問題一模一樣的子問題，永遠算不出答案（p.224）。結論是：
更一般地說，沒有東西能夠保證遞迴呼叫的輸入比原來的輸入更容易求解。（p.224）
這個例子給我們的教訓是，在設計演算法的訣竅中，還需要另外一個步驟：終止論證。這個步驟解釋對於每種輸入為什麼程式產生輸出，以及函式是怎樣實現這種思想的；或者給出警告，說明在什麼情況下程式可能不會終止。（p.224）
步驟（語言無關）
-
資料分析與設計——先選定「用什麼資料表示這個問題」。表示法會左右你怎麼想這個問題（p.222）。
-
合約、用途、頭部——除了寫清楚做什麼，還要多寫一段：「用途說明不僅要指明函式做了什麼，還應該包括一個註釋，用普通的術語解釋它是如何工作的。」（p.223）因為生成步驟跟資料定義的結構無關，讀者沒有別的線索。
-
例子——跟一般訣竅不同，這裡的例子要示範過程而不只是輸入→輸出：「對於演算法來說，例子應當闡明，對於給定的輸入，演算法是怎樣運行的。」（p.223）圖 26.1 把這階段的任務拆成三件事：構造並顯示平凡可解問題的例子、構造並顯示需要處理的例子、舉例說明如何（完整地）處理例子（p.224）。
-
模板——所有演算法共用同一個骨架（p.223）：先問「這個問題是不是平凡可解？」是的話直接給解；不是的話，生成一個或多個新問題，各自遞迴，最後把解組合起來（過程中可能還要用到原問題的資訊）。
-
本體：回答四個關鍵問題（p.223）——模板只是提示，真正要填的是這四題：
- 什麼是平凡可解問題？
- 相應的解是什麼？
- 如何生成新的、比原來的問題更容易解的問題？是生成一個新問題，還是若干個？
- 原問題的解是不是就是（某一個）新問題的解？或者需要把新問題的解連接起來？如果是，還需要原問題中的任何資訊嗎？
-
測試——照舊，但記得「測試並不能證實函式對所有可能的輸入都能正確工作」（p.223）。這正是為什麼要有第 7 步。
-
★ 終止論證——圖 26.1 為這一階段列的目標與任務是（p.224）：
階段 目標 任務 終止 證明演算法對於任何可能的輸入都會終止 說明遞迴呼叫的輸入要比原輸入短 書對 quick-sort 給的示範論證（p.225）：
在每一個步驟中，quick-sort 使用 smaller-items 和 larger-items 把表分為兩個部分。這兩個函式都給出一個比輸入（第二個參數）更短的表。因此，quick-sort 的每一步遞迴呼叫都讀入一個比原來輸入嚴格更短的表。最終，quick-sort 會讀入 empty，並返回 empty。
驗收標準很硬：「如果沒有這樣一個論證，我們就認為演算法是不完整的。」（p.225）
額外紅利：好的終止論證會生出新的平凡情況
這是最容易被略過、卻最划算的一點（p.225）：
一個良好的終止論證有時可能會揭示出其他的終止情況。
書的例子：寫 quick-sort 的終止論證時會發現，對任意的 N，把 (list N) 拿去分割，比 N 小的和比 N 大的都是空表——所以單元素表的答案就是它自己。把這個觀察補成一條新的終止子句（判斷「其餘部分是不是空的」），演算法就少繞一大圈。寫論證不只是事後補證明，它會回頭改良演算法本身。
🧪 我實際套用的紀錄
- （待填）
⚠️ 注意 / 什麼時候不適用
- 預設不要用它。 書的經驗法則是（p.229）：「大部分的函式使用的是結構遞迴；只有少數函式使用生成遞迴。當我們遇到既可以使用結構遞迴，又可以使用生成遞迴的情況，最好的方法通常是先使用結構遞迴，如果這樣得到的程式運行起來太慢，再探究是否可以選用生成遞迴。」
- 不要以為「生成遞迴 = 比較快」。 書給了三個理由潑冷水（p.229）：① 設計得很好的演算法也不總是比較快——quick-sort 只有處理較長的表才有優勢，短表反而是普通的 sort 比較快，而設計得差的演算法「可能會給程式的性能帶來災難」；② 用結構遞迴的訣竅設計總是比較簡單，設計演算法「通常需要深奧的數學知識」；③ 結構遞迴的函式別人一看就懂，演算法「必須有人給你解釋生成的步驟」。
- 設計演算法本來就不是照本宣科。 書說「我們最好稱之為發明一種演算法，而不是設計一種演算法。發明演算法需要一種新的洞察力」（p.216），而且「新的、複雜的演算法通常總是由數學家和理論計算機科學家設計的」——程式設計者的定位是能自己造簡單的、並看得懂科學家造的複雜的。
- 模板本身分辨不出兩者。 演算法模板太一般，把結構遞迴也涵蓋進去了（把「是否平凡可解」換成「是否為空表」、把「生成問題」換成「取其餘部分」，它就退化成一般的表處理模板，p.226）。所以別靠形狀判斷，要靠「遞迴的輸入是從哪來的」判斷。
- 兩者的真正分野（p.226）：「一種設計方法基本上只依賴於系統的資料分析；另一種設計方法需要對問題解決過程本身深刻的——通常是數學上的——洞察力。一種設計方法引導程式設計師給出自然終止的函式；另一種設計方法需要程式進行終止論證。」
- 真的決定用生成遞迴時，交付門檻是兩件事：「使用好的例子來說明問題的生成，並給出正確的終止論證。」（p.229）
🔗 相關工具
- 工具-資料驅動的模板推導 —— 對照組：那張講結構遞迴（模板順著資料定義長出來、自然終止），這張講它不管用的時候。先讀那張再讀這張。
- 工具-設計訣竅 —— 本卡是它的「演算法版」：同樣六個階段，但每階段的內容不同，而且多第七步終止論證。
- 工具-演算法設計策略 —— 出自《演算法圖解》，講選哪種策略（分治／貪婪／DP）；本卡出自 HtDP，講選了之後怎麼把它寫成一個保證會停的函式。互補，不重疊。
- 工具-遞迴式與主定理 —— 出自《演算法導論》，回答「這個遞迴要跑多久」；本卡只回答「這個遞迴會不會停」。要效能分析找那張，要正確性/終止性找這張。
- 程式設計方法 —— 來源書（第 25、26 章）。