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

将触发有关两个非尾递归调用的编译器警告。

相互递归函数

有时函数 是相互递归的，这意味着调用形成一个圆圈，其中一个函数调用另一个函数，而后者又调用第一个函数，其中任意数量的调用介于两者之间。 必须在一个绑定中定义此类函数，使用and关键字将它们链接在一let起。

以下示例显示了两个相互递归函数。

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要递归的 -bound 值。 这有时是为日志记录完成的。 使用 F# 5 和 nameof 函数，可以执行以下作：

let rec nameDoubles = nameof nameDoubles + nameof nameDoubles

另请参阅

• 函数