递归函数：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
...
备注
在 F# 语言中，递归函数（调用自身的函数）使用 rec 关键字标识。 rec 关键字使 let 绑定的名称在其主体中可用。
下面的示例演示一个递归函数，该函数使用数学定义计算第 n 个斐波纳契数。
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 关键字。
尾递归
对于某些递归函数，需要将更“纯粹”的定义重构为尾递归。 这可以防止不必要的重新计算。 例如，可以重写以前的斐波纳契数生成器，如下所示：
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
生成斐波那契数是“朴素”算法的一个很好的例子，它在数学上是纯粹的，但在实践中效率低下。 虽然这是一个更复杂的实现，但在 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
