erlang - 尾递归归并排序算法

我已经实现了递归归并排序算法:

-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"template"——我理解我将如何实现一个可以根据一系列定义的 TR 函数，例如——那只会将函数的参数向上移动到系列中，但是对于我们有条件地将子列表合并到列表其余部分的自然递归的情况，我很无知。

因此，我想问:

1)如何制作mergesort/3 TR？

2)我可以使用哪些资源来深入了解erlang尾递归？

最佳答案

您的归并排序不是尾递归的，因为在 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 合并排序示例。这是自下而上的思维方式。我使用了您模块中的 merge/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 。

关于erlang - 尾递归归并排序算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27087622/