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 -> let 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屋！