F#Tail递归函数示例

从一个简单的任务开始,比如在列表中将项目从“a”映射到“b”。我们想写一个有签名的函数

val map: ('a -> 'b) -> 'a list -> 'b list

在哪里?

map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]

从…开始 无尾递归

let rec map f = function
    | [] -> []
    | x::xs -> f x::map f xs

这不是尾部递归,因为函数在进行递归调用后仍有工作要做。 :: List.Cons(f x, map f xs) .

如果我将最后一行重新编写为 | x::xs -> let temp = map f xs; f x::temp --显然,它在递归调用之后工作。

使用 累加器变量

let map f l =
    let rec loop acc = function
        | [] -> List.rev acc
        | x::xs -> loop (f x::acc) xs
    loop [] l

我们在变量中建立一个新的列表 acc . 因为列表是反向建立的,所以在将输出列表返回给用户之前,我们需要反转输出列表。

要更简洁地编写代码:

let map f l =
    let rec loop cont = function
        | [] -> cont []
        | x::xs -> loop ( fun acc -> cont (f x::acc) ) xs
    loop id l

自从打电话给 loop 和 cont

续 被一个新的连续性捕获,而另一个连续性又被另一个连续性捕获,从而形成一种树状数据结构,如下所示:

(fun acc -> (f 1)::acc)
    ((fun acc -> (f 2)::acc)
        ((fun acc -> (f 3)::acc)
            ((fun acc -> (f 4)::acc)
                ((fun acc -> (f 5)::acc)
                    (id [])))))

它按顺序建立一个列表,而不需要您反转它。

值得一提的是,开始以非尾部递归方式编写函数,它们更易于阅读和使用。

如果你有一个大的列表要浏览,使用一个累加器变量。

如果你找不到一种方便的方法来使用累加器,而且你也没有其他的选择,那就使用continuations。我个人认为不琐碎,大量使用连续体很难阅读。

试图用比其他例子更简短的解释:

let rec foo n =
    match n with
    | 0 -> 0
    | _ -> 2 + foo (n-1)

let rec bar acc n =
    match n with
    | 0 -> acc
    | _ -> bar (acc+2) (n-1)

在这里, foo 福 2+foo(n-1)

然而, bar 是的,因为 酒吧 酒吧

更改中的最后一行 酒吧 | _ -> 2 + (bar (acc+2) (n-1)) 会再次破坏尾部递归的函数,因为 2 + 导致需要采取的行动

这里有一个更明显的例子,将其与通常对阶乘所做的比较。

let factorial n =
    let rec fact n acc =
        match n with
        | 0 -> acc
        | _ -> fact (n-1) (acc*n)
    fact n 1

这个有点复杂,但是我们的想法是使用一个累加器来保持运行计数,而不是修改返回值。

此外,这种包装方式通常是一个好主意,这样您的调用者就不必担心为累加器设置种子(请注意,事实是函数本地的)

下面是用无尾递归函数和尾递归函数来计算斐波那契数。

无尾递归版本

let rec fib = function
    | n when n < 2 -> 1
    | n -> fib(n-1) + fib(n-2);;

尾部递归版本

let fib n =
    let rec tfib n1 n2 = function
    | 0 -> n1
    | n -> tfib n2 (n2 + n1) (n - 1)
    tfib 0 1 n;;  

tfib 0 1 n 到
tfib 0I 1I n 利用F中的Numerics.BigInteger结构#