對遞迴呼叫的歸納（induction on recursive calls）

一個遞迴程序處理大輸入的方式，是對更小的輸入呼叫自己，再把結果合併起來。當函式呼叫自己、甚至呼叫很多次時，你怎麼信任它的答案？你用的，正是你會給同事的那種信任：假設每個遞迴呼叫對它（更小的）輸入回傳正確答案，再檢查你是否把這些正確答案組裝成整體的正確答案。這就是對遞迴呼叫的歸納——對輸入規模做歸納，而遞迴呼叫扮演歸納假設的角色。

做法有兩部分，正好對應歸納法。基底情形：非遞迴情形（小到可以直接回答的輸入，例如空串列或單一元素串列）直接回傳正確答案。歸納步驟：假設每個對嚴格更小輸入所做的遞迴呼叫都回傳正確結果（這是歸納假設），再證明合併步驟能把它們轉成當前輸入的正確結果。以合併排序為例：基底情形，長度 <= 1 的串列本就已排序；步驟，兩個遞迴呼叫分別排好左半與右半（由歸納假設），而合併能把兩個已排序的半邊正確交織成一個已排序的整體——所以結果是排序好的。因為每個呼叫都對嚴格更小的輸入，這串假設會在基底情形見底；它其實就是對規模做的強歸納法。

有兩件事讓這套做法嚴謹又安全。第一，遞迴必須在每次呼叫時嚴格縮小輸入，這樣才不會永遠遞迴下去——這個遞減的度量同時也證明了停機性。第二，你必須單獨檢查合併步驟，把遞迴結果當成單純就是正確的黑盒子。一個微妙卻常見的錯誤，是對其實沒有變小的輸入假設正確性（例如對相同規模遞迴），那會讓歸納變成循環論證，程序也可能不會停機。