递归 属于

关于 递归

递归是指一个事物能够用自身来定义自身的能力。在 F# 中，递归最常见的体现形式是递归函数，也就是自己调用自己的函数。

递归函数至少需要一个基准情况，并且至少需要一个递归情况。基准情况不再调用函数，直接返回一个值。递归情况会再次调用函数，同时修改输入，使它最终能匹配到基准情况。

递归函数的定义方式和普通函数一样，只是多了一个rec修饰符。没有这个修饰符，函数就无法调用自身，任何这样的尝试都会导致编译错误。因此，递归必须显式启用。

let rec factorial x =
    // Base case
    if x = 1 then
        1
    // Recursive case
    else
        x * factorial (x - 1)

数组常常用递归来处理。例如，下面是用递归计算数组长度的方法：

let rec length list =
    match list with
    | [] -> 0
    | x::xs -> 1 + length xs

length [1; 2; 3]
// => 3

许多内置函数都是用递归定义的。

递归函数可能带来的一个问题是，每一次（递归）函数调用都会在栈上产生分配，使栈不断增长。由于栈的内存有限，递归调用次数很多的函数可能会抛出StackOverflowException。到底多少次递归调用会触发这种情况，取决于多种因素，例如栈上可用的内存，以及每次函数调用在栈上占用多少数据。

防止递归函数把栈撑爆的最好方法，就是把它们写成尾递归函数。当函数是尾递归时，编译器可以优化它生成的代码，使得每次递归函数调用都不再需要在栈上额外分配空间。尾递归函数只有一条规则：递归函数调用的结果必须由函数直接返回，不能再有任何额外代码去处理这个递归调用的结果。最常见的做法是创建一个辅助函数，让它额外接收一个累加器实参，这个实参在每次递归调用时更新，并在递归结束时返回。这个页面非常详细地介绍了编译器处理尾递归函数的过程。

下面是数组长度函数的尾递归版本：

let rec lengthRecursive acc list =
    match list with
    | [] -> acc
    | x::xs -> lengthRecursive (acc + 1) xs

let length list = lengthRecursive 0 list

把递归的辅助函数定义为嵌套函数是很常见的做法，这样调用方就看不到函数的递归本质：

let length list =
    let rec lengthRecursive acc remainder =
        match remainder with
        | [] -> acc
        | x::xs -> lengthRecursive (acc + 1) xs

    lengthRecursive 0 list

F# 通过可区分联合类型支持递归类型。递归的可区分联合类型中，会有一个或多个分支的数据引用这个可区分联合类型自身。和递归函数一样，递归类型也必须有一个基准情况。与递归函数不同的是，递归类型不使用rec关键字。

type RussianDoll =
    | Doll                 // Base case
    | Layer of RussianDoll // Recursive case

下面是一个操作上述递归类型的（非尾递归）函数：

let layers doll =
    match doll with
    | Doll -> 0 // Base case
    | Layer innerDoll -> 1 + layers innerDoll // Recursive case

layers (Layer Doll)
// => 1