怎么做列表串联"正确"的方式(使用尾递归)

Question

我正在进行以下Erlang练习:

编写一个函数,给定一个列表列表,将它们连接起来.例:

concatenate([[1,2,3], [], [4,five]]) ? [1,2,3,4,five].

我想出了这个:

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate([T|Tail])].

哪个有效,但我注意到我正在做这[T|Tail]件事.

第一个问题

这仍然被认为是直接递归吗？

在那之后,我摆脱了它[T|Tail]并使用了累加器(如下所示).

第二个问题

现在第二个代码是否考虑了尾递归？

这本书提示使用辅助函数(第二个代码正在做),但它看起来相当冗长.是因为我错过了什么吗？

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate(T,Tail)].

concatenate([],Tail) ->
    concatenate(Tail);
concatenate([H],Tail) ->
    [H|concatenate(Tail)];
concatenate([H|T],Tail) ->
    [H|concatenate(T,Tail)].

Answer 1

正如@Yasir解释的那样,它们都不是尾递归的,但我不会担心它(见下文).使用辅助函数可以通过消除输入列表的部分重建来改进代码.您的代码有点冗长,可以通过删除一些不必要的子句来简化,conc/1并始终调用conc/2:

conc([H|T]) -> conc(H, T);
conc([]) -> [].

conc([H|T], Rest) -> [H|conc(T, Rest)];
conc([], Rest) -> conc(rest).

然后使用累加器拆分尾递归版本将成为:

conc(List) -> conc(List, []).

conc([H|T], Acc) -> conc(H, T, Acc);
conc([], Acc) -> lists:reverse(Acc).

conc([H|T], Rest, Acc) -> conc(T, Rest, [H|Acc]);
conc([], Rest, Acc) -> conc(Rest, Acc).

现在,这些天的速度差异比过去少得多,请参见神话:尾递归函数比递归函数快很多,所以最好使用看起来更清晰的样式.我个人不想使用累加器,除非我必须这样做.

Answer 2

两个[H|concatenate([T|Tail])]和[H|concatenate(T,Tail)]不尾递归调用,因为无论呼叫是另一种表达的一部分,并且因此控制将返回到的表达,其中包括对您的呼叫concatenate/1,2.

正确的尾递归conc可能看起来像:

-module(concat).
-export([concatenate/1]).

concatenate(L) ->
     conc(L, []).

conc([], Acc) ->
     lists:reverse(Acc);
conc([[H|T] | L1], Acc)->
     conc([T|L1], [H|Acc]);
conc([[] | L1], Acc) ->
     conc(L1, Acc).

在这里,conc/2对自身的调用是函数体中的最后一个操作,函数永远不会返回.

编辑:如果我们忘记了非尾递归调用的优化,@ Robert说,目前,由于调用函数的返回地址传递到堆栈(堆？),我们最终会因内存溢出而结束.如果你调用非尾递归函数,在一个内存大小不足的系统上传递一个相当长的列表来保存这么多的返回地址,就会发生这种情况.