瞭解F＃尾遞歸

Question

最近，我正在學習F＃。 我嘗試以不同的方式解決問題。 像這樣：

(* 

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

爲什麼V2和V3的結果是不同的？

Answer 1

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))實際上是該函數的聲明的最後的聲明。

順便說一句，你提供的代碼是一個很好的例子來顯示概念尾遞歸函數。瞭解這些示例代碼的一種方法是在小案例上工作，就像我在上面的兩個插圖中所做的那樣。在處理一些小案例之後，你會更深入地理解這個概念。