遞迴函式：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
