3
我已經實現了一個遞歸算法歸併:尾遞歸算法歸併
-module(ms).
-import(lists,[sublist/3,delete/2,min/1,reverse/1]).
-export([mergesort/1]).
mergesort([])->
[];
mergesort([N])->
N;
mergesort(L)->
mergesort(split(1,L),split(2,L),[]).
mergesort(L1,L2,[])->
case {sorted(L1),sorted(L2)} of
{true,true}->
merge(L1,L2,[]);
{true,false}->
merge(L1,mergesort(split(1,L2),split(2,L2),[]),[]);
{false,true}->
merge(mergesort(split(1,L1),split(2,L1),[]),L2,[]);
{false,false}->
merge(mergesort(split(1,L1),split(2,L1),[]),mergesort(split(1,L2),split(2,L2),[]),[])
end.
merge([],[],R)->
reverse(R);
merge(L,[],R)->
merge(delete(min(L),L),[],[min(L)|R]);
merge([],L,R)->
merge([],delete(min(L),L),[min(L)|R]);
merge([H1|T1],[H2|T2],R) when H1 < H2 ->
merge(T1,[H2|T2],[H1|R]);
merge([H1|T1],[H2|T2],R) when H1 >= H2 ->
merge([H1|T1],T2,[H2|R]).
split(1,L)->
sublist(L,1,ceiling(length(L)/2));
split(2,L)->
sublist(L,ceiling(length(L)/2+1),length(L)).
ceiling(X) when X < 0 ->
trunc(X);
ceiling(X) ->
T = trunc(X),
case X - T == 0 of
true -> T;
false -> T + 1
end.
但是我的事實,mergesort/3
不是尾遞歸(TR)厭煩,並且是冗長。
我想這裏的問題是,我不是特別意識到TR'模板',我會在這裏使用 - 我明白我將如何實現TR功能,可以根據一系列的定義,例如 - 這隻會將參數移到該系列的函數中,但對於我們將一個子列表有條件地合併到列表的其餘部分的自然遞歸的情況,我是無知的。
因此,我想問一下:
1)我怎樣才能讓mergesort/3
TR?
2)我可以使用哪些資源深入理解erlang尾遞歸?