F#尾递归函数示例

Question

我是F#的新手,正在阅读有关尾递归函数的内容,希望有人可以给我两个不同的函数foo实现 - 一个是尾递归的,另一个不是我可以更好地理解这个原理.

Answer 1

从一个简单的任务开始,比如从列表中的'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- 显然它在递归调用之后正在工作.

使用accumulator变量使其尾递归:

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最后调用的函数没有额外的工作,因此它们是尾递归的.

这是有效的,因为延续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 [])))))

它会按顺序构建一个列表而不需要你反转它.

为了它的价值,开始以非尾递归的方式编写函数,它们更容易阅读和使用.

如果您有一个大的列表,请使用累加器变量.

如果您无法以方便的方式找到使用累加器的方法,并且您没有任何其他选项可供使用,请使用延续.我个人认为难以读懂的非平凡,大量使用延续.

Answer 2

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

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不是尾递归,因为foo必须递归调用foo才能评估"2 + foo(n-1)"并返回它.

bar是尾递归的,因为bar不必使用递归调用的返回值来返回值.它可以让递归调用的bar立即返回其值(不通过调用堆栈返回所有方式).编译器通过将递归重写为循环来看到这个和"作弊".

将bar中的最后一行更改为"| _ - > 2+(bar(acc + 2)(n-1))"会破坏尾部递归.

Answer 3

这是一个更明显的例子,将它与通常为阶乘做的事情进行比较.

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

这个有点复杂,但想法是你有一个累加器来保持运行计数,而不是修改返回值.

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

Answer 4

我也在学习F#。以下是计算斐波那契数的非尾递归和尾递归函数。

非尾递归版本

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;;  

注意：由于 fibanacci 数可能增长得非常快，因此您可以替换最后一行tfib 0 1 n以
tfib 0I 1I n利用 F# 中的 Numerics.BigInteger 结构