递归函数：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

请参阅

• 函数