「全麥編程」的觀念鼓勵我們以小組件組織出大程式。 但這些個別組件該如何實作呢？或著，沒有合用的組件時該怎麼辦？ 我們可以回到更基礎的層次，用遞迴(recursion)定義它們。 「遞迴」意指一個值的定義又用到它本身，是數學中常見的定義方式。 在早期的程式設計教材中，遞迴常被視為艱澀、難懂、進階的主題。 但在函數程設中，遞迴是唯一可使程式不定次數地重複一項計算的方法。 一旦跨過了門檻，遞迴其實是個很清晰、簡潔地描述事情的方式。

對於遞迴，許多初學者一方面不習慣、覺得如此構思程式很違反「直覺」，另一方面也納悶：以自己定義自己，到底是什麼意思？ 這兩個難處其實都談到了好問題。 對於前者，我們希望發展一些引導我們構思遞迴程式的思路；希望有了這些依據，能使寫遞迴程式變得直覺而自然。 關於後者，其實並非所有遞迴定義都有「意思」 --- 有些「不好」的遞迴並沒有定義出東西。我們討論遞迴的意義時必須限定在「好」的、有意義的程式上。最好有些方式確保我們寫出的遞迴定義是好的。

在本章我們將討論一種型式較單純的遞迴：歸納(induction)。 對上述兩個問題，本章的回應是：先有歸納定義出的資料結構，再依附著該資料結構撰寫歸納定義的程式，是一種思考、解決程式問題的好方法，也是一種理解遞迴程式的方式。 此外，依循這種方法也能確保該定義是「好」的。 我們將從數學歸納法出發，發現歸納程式與數學歸納法的相似性 --- 寫程式和證明其實是很相似的活動。

本書以 Haskell 為學習工具，但在之後的幾章，我們僅使用 Haskell 的一小部分。 Haskell 支援無限大的資料結構，也允許我們寫出不會終止的程式。 但我們將假設所有資料結構都是有限的（除非特別指明），所有函數皆會好好終止（也就是說函數都是「全函數(total function)」--- 對每一個值，都會好好地算出一個結果，不會永遠算下去，也不會丟回一個錯誤）。這麼做的理由將在本章解釋。