F# Tail Recursive Function Example

我是F＃的新手，并且正在阅读关于尾递归函数的内容，并希望有人能够给我两个不同的函数foo实现 - 一个是尾递归函数，另一个不是我能更好地理解这个原理。

---

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

Where

map (fun x -> x * 2) [1;2;3;4;5] == [2;4;6;8;10]

Start with non-tail recursive version:

let rec map f = function
    | [] -> []
    | x::xs -> 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(fx, map f xs) .

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; fx::temp | x::xs -> let temp = map f xs; fx::temp | x::xs -> let temp = map f xs; fx::temp -- obviously its doing work after the recursive call.

Use an accumulator variable to make it tail recursive:

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

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

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

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.

---

An attempt at a shorter explanation than in the other examples:

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 is not tail recursive, because foo has to call foo recursively in order to evaluate "2+foo(n-1)" and return it.

bar is tail recursive, because bar doesn't have to use the return value of the recursive call in order to return a value. It can just let the recursively called bar return its' value immediately (without returning all the way up though the calling stack). The compiler sees this and 'cheats' by rewriting the recursion into a loop.

Changing the last line in bar to "| _ -> 2+(bar (acc+2) (n-1))" would destroy the tail end recursiveness.

---

Here is a more obvious example, compare it to what you would normally do for a factorial.

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

This one is a bit complex, but the idea is that you have an accumulator that keeps a running tally, rather than modifying the return value.

Additionally, this style of wrapping is usually a good idea, that way your caller doesn't need to worry about seeding the accumulator (note that fact is local to the function)

链接地址: http://www.djcxy.com/p/2280.html

上一篇: 生成尾部调用操作码

下一篇: F＃尾递归函数示例