尾递归算法归并

我已经实现了一个递归算法归并：尾递归算法归并

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

来源

2014-11-23 category

您的合并排序不是尾递归，因为在mergesort/3中调用的最后一个函数是merge/3。你调用mergesort作为合并的参数，所以堆栈必须增长 - upper被称为mergesort/3还没有完成，它的堆栈帧不能被重用。要用TR方法编写它，你需要尽可能地将它想象得更加紧凑。每个TR功能都可以轻松地重复写入循环中的迭代。试想一下：

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。

来源

2014-11-23 18:59:09

尾递归算法归并

回答

相关问题