Recursion 入門

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

遞迴函式

遞迴函式有兩個部分:

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

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

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

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

遞迴型別

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

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

T = …… T …

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

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

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

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