40

我是 F# 的新手，正在阅读尾递归函数，希望有人能给我函数 foo 的两种不同实现——一种是尾递归的，另一种不是，这样我可以更好地理解原理。

4

5 回答 5

61

从一个简单的任务开始，例如将列表中的项目从 '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

由于对loopand的调用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 [])))))

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

对于它的价值，开始以非尾递归方式编写函数，它们更易于阅读和使用。

如果您有一个大列表要查看，请使用累加器变量。

如果您找不到一种方便地使用累加器的方法，并且您没有任何其他选择，请使用延续。我个人认为难以阅读的非平凡的、大量使用的延续。

于 2010-07-14T16:46:45.320 回答
30

尝试比其他示例更简短的解释：

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))的内容会再次破坏尾递归函数，因为这会导致递归调用完成后2 +需要执行的操作。

于 2010-07-14T16:36:31.923 回答
10

这是一个更明显的示例，将其与您通常对阶乘所做的比较。

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

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

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

于 2010-07-14T20:55:51.290 回答
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;;

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

于 2015-12-16T00:38:13.237 回答
2

另外，在测试的时候，别忘了在Debug模式下编译的时候，间接尾递归（tailcall）默认是关闭的。这可能导致尾调用递归在 Debug 模式下溢出堆栈，但在 Release 模式下不会。

于 2010-07-14T19:08:51.407 回答