F#尾递归函数示例

Question

F#尾递归函数示例

44

我刚开始接触 F#，正在阅读关于尾递归函数的内容，并希望有人可以给我两个不同实现方式的 foo 函数，一个是尾递归的，另一个不是，以便我更好地理解原则。

- Mark Pearl

1

Chris Smith写了一篇不错的文章，链接在这里：http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx。 - elmattic

谢谢 - 他的帖子很棒！ - Mark Pearl

虽然尾递归适用于函数，但是针对涉及多个函数的相同问题，请检查CPS。 - Guy Coder

2

Chris Smith的博客文章位置已更新：https://learn.microsoft.com/en-au/archive/blogs/chrsmith/understanding-tail-recursion - malcolmp

5个回答

32

相较于其他示例，这是一种更简短的解释尝试：

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) 并返回它，foo 必须要递归调用自身。

然而，bar 是尾递归的，因为 bar 不需要使用递归调用的返回值就可以返回一个值。它只需让被递归调用的 bar 立即返回其值（而不是一直返回到调用堆栈上）即可。编译器会看到这个优化，把递归改写成循环。

将 bar 中的最后一行改为类似于 | _ -> 2 + (bar (acc+2) (n-1)) 的语句会破坏函数的尾递归性，因为 2+ 需要在递归调用结束后执行。

- John Reynolds

4

谢谢Batibix提供简洁的例子。 - Mark Pearl

11

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

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

这个有点复杂，但主要思想是使用累加器来保持一个持续更新的总数，而不是修改返回值。

另外，这种包装风格通常是一个好主意，这样你的调用者就不需要担心如何初始化累加器（注意，该事实仅局限于函数内部）。

- Guvante

5

我也在学习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结构。

- leoflower

3

此外，在进行测试时，请不要忘记，当以调试模式编译时，默认情况下关闭了间接尾递归（tailcall）。这可能会导致在调试模式下尾递归溢出堆栈，但在发布模式下不会。

- TechNeilogy

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Juliet · Accepted Answer

从简单的任务开始，例如在列表中将项从'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是最后一个没有额外工作的函数调用，它们是尾递归的。

这是因为续延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。我个人认为，复杂的continuations使用难以阅读。