Понимание рекурсивный хвостом F#
Недавно, я изучаю 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 отличаются?
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 использует продолжение ], или, говоря простым языком, накопительная функция :
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)]
Вы можете увидеть разницу между накопительными переменными и накопительными функциями:
Использование накопительных переменных останавливается при последнем вызове, поскольку накопительная переменная сохраняет ответ . Однако функция накопления по-прежнему выполняет некоторую обратную работу после последнего вызова. Следует отметить, что использование накапливающих функций действительно является хвостовой рекурсией, поскольку рекурсивный вызов цикла t (fun ls -> accfun ((a, b, c) :: ls)) фактически является последним оператор этой функции.
Между прочим, предоставленный вами код является хорошим примером, демонстрирующим концептуальные рекурсивные функции хвоста. Один из способов понять этот пример кода - это работать с небольшими случаями , как я делал на двух приведенных выше иллюстрациях. Поработав над небольшими случаями, вы глубже поймете эту концепцию.