代码之家  ›  专栏  ›  技术社区  ›  kev

理解F#tail递归

  •  8
  • kev  · 技术社区  · 16 年前

    我试着用不同的方法解决问题。 这样地:

    (*
    
    [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的结果应该是一样的。 但是,我得到的结果如下:

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

    1 回复  |  直到 10 年前
        1
  •  11
  •   Yin Zhu    16 年前

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

    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使用 continuation 累积函数 :

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

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

    回溯 loop t (fun ls -> accfun ((a,b,c)::ls)) 实际上是 最后的

    顺便说一句,您提供的代码是一个很好的示例,可以展示递归函数的概念。理解这些示例代码的一种方法是 处理小案件