遞迴函式：rec 關鍵字

rec 關鍵字會與 let 關鍵字搭配使用，以定義遞迴函式。

語法

// Recursive function:
let rec function-name parameter-list =
    function-body

// Mutually recursive functions:
let rec function1-name parameter-list =
    function1-body

and function2-name parameter-list =
    function2-body
...

備註

遞迴函式是呼叫自身的函式，使用 rec 關鍵字以 F# 語言明確識別。 rec 關鍵字可讓 let 繫結的名稱在其主體中使用。

下列範例顯示使用數學定義計算第 n 個 Fibonacci 數字的遞迴函式。

let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

注意

在實務上，上一個範例所示的程式碼由於不必要地重新計算已計算過的值，因此並不理想。 這是因為它不是尾遞迴，本文將進一步說明。

方法會在定義的類型內隱含遞迴，這表示不需要新增 rec 關鍵字。 例如：

type MyClass() =
    member this.Fib(n) =
        match n with
        | 0 | 1 -> n
        | n -> this.Fib(n-1) + this.Fib(n-2)

不過，類別內的 let 繫結不會隱含遞迴。 所有 let 繫結函式都需要 rec 關鍵字。

尾遞迴

針對某些遞迴函式，必須將更「單純」的定義重構為尾遞迴。 這可防止不必要的重新計算。 例如，先前的 Fibonacci 數字產生器可以重寫如下：

let fib n =
    let rec loop acc1 acc2 n =
        match n with
        | 0 -> acc1
        | 1 -> acc2
        | _ ->
            loop acc2 (acc1 + acc2) (n - 1)
    loop 0 1 n

產生 Fibonacci 數字是數學上單純但實務上效率不佳之「簡易」演算法的絕佳範例。 雖然這是更複雜的實作，但在幾個層面會使其在 F# 中更有效率，同時仍保持以遞迴方式定義：

• 名為 loop 的遞迴內部函式，這是慣用的 F# 模式。
• 兩個累加器參數，可將累積值傳遞至遞迴呼叫。
• 檢查值 n 以傳回特定累加器。

如果此範例是使用迴圈反覆撰寫而成，程式碼看起來會很類似，但有兩個不同的值會累積數字，直到符合特定條件為止。

這是尾遞迴是因為遞迴呼叫不需要儲存呼叫堆疊上的任何值。 所有要計算的中間值都會透過內部函式的輸入來累積。 這也可讓 F# 編譯器將程式碼最佳化，就像您撰寫類似 while 迴圈的程式碼一樣快速。

撰寫 F# 程式碼通常會以遞迴方式處理具有內部和外部函式的程式碼，如上一個範例所示。 內部函式會使用尾遞迴，而外部函式則具有較佳的呼叫端介面。

從 F# 8.0 開始，您可以使用 TailCall 屬性明確陳述您打算定義尾遞歸函式給編譯程式的意圖。 然後，如果您的函式進行非尾遞歸呼叫，編譯程式將會警告您。 您可以在方法和模組層級函式上使用屬性。
例如，在第一個 fib 定義上使用：

[<TailCall>]
let rec fib n =
    match n with
    | 0 | 1 -> n
    | n -> fib (n-1) + fib (n-2)

會觸發兩個非尾遞歸呼叫的編譯程式警告。

相互遞迴函式

有時候函式是「相互遞迴」的，這表示呼叫會形成循環，其中一個函式會呼叫另一個函式，而此另一個函式會接著呼叫第一個函式，以及兩者之間任意數目的呼叫。 您必須在一個 let 繫結中定義所有這類函式，並使用 and 關鍵字將它們連結在一起。

下列範例顯示兩個相互遞迴函式。

let rec Even x = if x = 0 then true else Odd(x - 1)
and Odd x = if x = 0 then false else Even(x - 1)

遞迴值

您也可以定義要遞迴的 let 繫結值。 這樣做有時是為了記錄。 透過 F# 5 和 nameof 函式，您可以執行下列程式碼：

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

另請參閱

• 函數