F# 尾递归函数示例 [英] F# Tail Recursive Function Example

问题描述

我是 F# 的新手，正在阅读有关尾递归函数的内容，希望有人能给我提供两种不同的函数 foo 实现——一种是尾递归，另一种不是尾递归，以便我更好地理解原理.

I am new to F# and was reading about tail recursive functions and was hoping someone could give me two different implementations of a function foo - one that is tail recursive and one that isn't so that I can better understand the principle.

推荐答案

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

Start with a simple task, like mapping items from 'a to 'b in a list. We want to write a function which has the signature

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) 的语法糖.

This isn't tail recursive because function still has work to do after making the recursive call. :: is syntactic sugar for List.Cons(f x, map f xs).

如果我将最后一行重写为 |，该函数的非递归性质可能会更明显一些.x::xs ->让 temp = map f xs;f x::temp -- 显然它在递归调用之后工作.

The function's non-recursive nature might be a little more obvious if I re-wrote the last line as | x::xs -> let temp = map f xs; f x::temp -- obviously its doing work after the recursive call.

使用累加器变量使其尾递归:

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

这是我们在变量 acc 中建立一个新列表.由于列表是反向构建的，我们需要在将输出列表返回给用户之前将其反向.

Here's we're building up a new list in a variable acc. Since the list gets built up in reverse, we need to reverse the output list before giving it back to the user.

如果您有点头脑混乱，可以使用继续传递来更简洁地编写代码:

If you're in for a little mind warp, you can use continuation passing to write the code more succinctly:

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

Since the call to loop and cont are the last functions called with no additional work, they're tail-recursive.

这是可行的，因为延续 cont 被一个新的延续所捕获，而新的延续又被另一个延续所捕获，从而产生一种树状数据结构，如下所示:

This works because the continuation cont is captured by a new continuation, which in turn is captured by another, resulting in a sort of tree-like data structure as follows:

(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 [])))))

它会按顺序构建一个列表，而无需您将其反转.

which builds up a list in-order without requiring you to reverse it.

就其价值而言，开始以非尾递归方式编写函数，它们更易于阅读和使用.

For what its worth, start writing functions in non-tail recursive way, they're easier to read and work with.

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

If you have a big list to go through, use an accumulator variable.

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

If you can't find a way to use an accumulator in a convenient way and you don't have any other options at your disposal, use continuations. I personally consider non-trivial, heavy use of continuations hard to read.

这篇关于F# 尾递归函数示例的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！