Recursion 入門

遞迴是指根據自身定義的東西。在程式設計環境中，它是使用自稱函式或遞迴型別的實踐。

遞迴函式

遞迴函式有兩個部分：

• 一個或多個基本案例
• 遞迴步驟

因為遞迴函式呼叫自身，所以函式呼叫字串可以永遠繼續。為了確保函式終止必須包含基本情況。這些將告訴函式何時返回值而不是執行另一個遞迴呼叫。通常，遞迴函式將檢查它們對基本情況的輸入，並在達到基本情況時返回。如果尚未到達基本情況，則該函式將進入遞迴步驟。

遞迴步驟是函式呼叫自身的時間。許多遞迴函式將返回對遞迴呼叫的結果執行的一些計算。Fibonacci 序列示例證明了這一點。該函式遞迴呼叫自身兩次，然後返回這些呼叫的結果總和

遞迴的一個常見用途是在大型資料結構（例如樹和圖形）上導航和執行計算。這很有效，因為遞迴可以解決問題並解決較小的問題，並以解決更大問題的解決方案為基礎。遞迴的另一個常見用途是在沒有內建迴圈結構的語言（通常是函式語言）中執行迭代操作（迴圈）。

遞迴型別

遞迴型別的值是由相同型別的值組成的，或者表達方式不同：遞迴型別是根據自身定義的。例如，列表是遞迴型別，因為列表的每個子集本身都是一個列表。樹是另一個例子，因為節點從樹中移除，剩下的構造仍然是樹。

形式上，遞迴型別 T 的值集將由表單上的遞迴集方程式定義：

T = …… T …

遞迴集方程可以有許多解，但是這樣的方程總是具有最小解，其是每個其他解的子集。

作為一個實際例子，考慮這個 Haskell 定義的列表型別，

data List a = Nil | Cons a (List a)

意思是 a 的列表是空列表或包含’a’（列表的頭部）和另一個列表（尾部）的 cons 單元。