遞迴 在

關於 遞迴

某個事物能夠以自身來定義，這種能力稱為遞迴。在 F# 中，遞迴最常出現在遞迴函式裡，也就是會呼叫自身的函式。

一個遞迴函式至少需要一個基礎情況，以及至少一個遞迴情況。基礎情況會回傳一個值，而不會再次呼叫函式。遞迴情況會再次呼叫函式，並修改輸入，讓它終究會符合基礎情況。

遞迴函式的定義方式和一般函式相同，只是多了一個rec修飾詞。少了這個修飾詞，函式就無法呼叫自身，而任何嘗試這麼做的舉動都會導致編譯錯誤。因此，遞迴必須明確地選擇採用。

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

陣列經常以遞迴方式處理。舉例來說，以下示範如何用遞迴計算陣列的長度：

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

許多內建函式都是以遞迴定義的。

遞迴函式可能遇到的問題之一，是每一次（遞迴）函式呼叫都會在堆疊上配置記憶體，使堆疊不斷增長。由於堆疊的記憶體有限，使用大量遞迴呼叫的函式可能會擲回StackOverflowException。究竟多少次遞迴呼叫才會觸發這種行為，取決於多項因素，例如堆疊上可用的記憶體，以及每次函式呼叫在堆疊上佔用多少資料。

要避免遞迴函式讓堆疊溢位，最好的做法是把它們寫成尾端遞迴函式。當一個函式是尾端遞迴時，編譯器就能最佳化它的輸出，讓每次遞迴函式呼叫都不再需要額外在堆疊上配置記憶體。尾端遞迴函式只有一條規則：遞迴函式呼叫的結果必須直接從函式回傳，不能有任何額外的程式碼再去處理這個遞迴呼叫的結果。最常見的做法是建立一個輔助函式，多收一個累加器引數；這個引數會在每次遞迴呼叫時更新，並在遞迴結束時回傳。這個頁面非常詳細地說明編譯器如何處理尾端遞迴函式。

以下是計算陣列長度的尾端遞迴版本：

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

把遞迴的輔助函式定義成巢狀函式也很常見，這麼做可以對呼叫端隱藏函式的遞迴本質：

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F# 支援透過差別聯合型別實現的遞迴型別。遞迴差別聯合型別會有其中一個或多個案例在自己的資料中參照這個差別聯合型別本身。和遞迴函式一樣，遞迴型別也必須有一個基礎情況。和遞迴函式不同的是，遞迴型別不使用rec關鍵字。

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

以下是一個用來處理上述遞迴型別的（非尾端遞迴）函式：

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1