了解F#尾递归 [英] Understanding F# tail-recursive

问题描述

最近，我正在学习F#. 我试图以不同的方式解决问题. 像这样:

Recently, I'm learning F#. I try to solve problem in different ways. Like this:

(*

[0;1;2;3;4;5;6;7;8] -> [(0,1,2);(3,4,5);(6,7,8)]

*)

//head-recursive
let rec toTriplet_v1 list=
    match list with
    | a::b::c::t -> (a,b,c)::(toTriplet_v1 t) 
    | _ -> []

//tail-recursive
let toTriplet_v2 list=
    let rec loop lst acc=
        match lst with
        | a::b::c::t -> loop t ((a,b,c)::acc)
        | _ -> acc
    loop list []

//tail-recursive(???)
let toTriplet_v3 list=
    let rec loop lst accfun=
        match lst with
        | a::b::c::t -> loop t (fun ls -> accfun ((a,b,c)::ls))
        | _ -> accfun []
    loop list (fun x -> x)

let funs = [toTriplet_v1; toTriplet_v2; toTriplet_v3];
funs |> List.map (fun x -> x [0..8]) |> List.iteri (fun i x -> printfn "V%d : %A" (i+1) x)

我认为V2和V3的结果应该相同. 但是，我得到以下结果:

I thought the results of V2 and V3 should be the same. But, I get the result below:

V1 : [(0, 1, 2); (3, 4, 5); (6, 7, 8)]
V2 : [(6, 7, 8); (3, 4, 5); (0, 1, 2)]
V3 : [(0, 1, 2); (3, 4, 5); (6, 7, 8)]

为什么V2和V3的结果不同?

推荐答案

V2使用标准的累加变量完成尾递归:

V2 uses standard accumulating variable to get tail recursion done:

loop ([0;1;2;3;4;5;6;7;8], []) ->
  loop ([3;4;5;6;7;8], [(0,1,2)]) ->
    loop ([6;7;8], [(3,4,5), (0,1,2)]) ->
      loop ([], [(6,7,8), (3,4,5), (0,1,2)]) ->
        [(6,7,8), (3,4,5), (0,1,2)]

V3使用延续，或者用简单的英语说，是累加功能 >:

V3 uses continuation, or in plain English, an accumulating function:

loop ([0;1;2;3;4;5;6;7;8], x->x) ->
  loop ([3;4;5;6;7;8], x->(0;1;2)::x) ->
    loop ([6;7;8], x->(3;4;5)::x) ->
      loop ([], x->(6,7,8)::x) ->
        [(6,7,8)]  // x->(6,7,8)::x applies to []
    ->
      [(3,4,5);(6,7,8)] // x->(3,4,5)::x applies to [(6,7,8)]
  ->
    [(0,1,2);(3,4,5);(6,7,8)] // x->(0,1,2)::x applies to [(3,4,5);(6,7,8)]

您可以看到累加变量和累加函数之间的区别:

You can see the difference between accumulating variables and accumulating functions:

使用累加变量会在最后一次调用时停止，因为累加变量会存储答案.但是，累积功能在最后一次调用后仍会执行某些回溯工作.应当注意，使用累加函数确实是尾递归，因为递归调用loop t (fun ls -> accfun ((a,b,c)::ls))实际上是该函数的 last 语句.

Using accumulating variables stops at the last call as the accumulating variable stores the answer. However, the accumulating function still does some backtrack work after the last call. It should be noticed that using accumulating functions is indeed tail recursive as the recursive call loop t (fun ls -> accfun ((a,b,c)::ls)) is actually the last statement of this function.

顺便说一句，您提供的代码是展示概念尾部递归函数的一个很好的例子.理解这些示例代码的一种方法是像上两个插图中那样处理小案例.在处理了一些小案例之后，您将更深入地了解该概念.

Btw, the code you provided is a good example to show the concept tail recursive functions. One way to understand these sample code is to work on small cases as I did in the above two illustrations. After working on some small cases, you will understand the concept deeper.

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