尾递归合并排序算法

Question

我实现了一个递归合并排序算法：

-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 尾递归？

Answer 1

您的合并排序不是尾递归的，因为在 mergesort/3 中调用的最后一个函数是 merge/3。你调用 mergesort 作为合并的参数，所以堆栈必须增长 - 称为 mergesort/3 的上层尚未完成，它的堆栈帧不能重用。要用 TR 方法编写它，您需要尽可能多地考虑它。每个 TR 函数都可以轻松重写为迭代 while 循环。考虑：

loop(Arg) ->
    NewArg = something_happens_to(Arg),
    loop(NewArg) or return NewArg.

和：

data = something;
while(1){
    ...
    break loop or modify data block
    ...
} // data equals to NewArg at the end of iteration

这是我的 TR 合并排序示例。这是自下而上的思维方式。我使用了您模块中的合并/3 函数。

ms(L) ->
    ms_iteration([[N] || N <- L], []).
ms_iteration([], []) -> % nothing to do
    [];
ms_iteration([], [OneSortedList]) -> % nothing left to do
    OneSortedList;
ms_iteration([], MergedLists) ->
    ms_iteration(MergedLists, []); % next merging iteration
ms_iteration([L], MergedLists) -> % can't be merged yet but it's sorted
    ms_iteration([], [L | MergedLists]);
ms_iteration([L1, L2 | ToMergeTail], MergedLists) -> % merging two sorted lists
    ms_iteration(ToMergeTail, [merge(L1, L2, []) | MergedLists]).

这里解释得很好：http://learnyousomeerlang.com/recursion.