并不是所有的时候都应该选择尾递归

要实现一个函数，参数是一个list，结果是将list里每个数字都+1，返回一个新的list，会怎么实现呢？

 

看代码，哪个函数性能最好？（除了add2，因为他的结果是不正确的）

-module(t).

-compile(export_all).

add1([]) -> [];
add1([H|T]) -> [H+1|add1(T)].

add2(R) -> add(R,[]).

add3(R) -> lists:reverse(add(R,[])).

add4([]) -> [];
add4(L) -> lists:map(fun(X) -> X+1 end,L).

add([],R) -> R;
add([H|T],R) -> add(T,[H+1|R]).

t(N) ->
   L = lists:seq(1,N),
   {T1,_}=timer:tc(a,add1,[L]),
   {T2,_}=timer:tc(a,add2,[L]),
   {T3,_}=timer:tc(a,add3,[L]),
   {T4,_}=timer:tc(a,add4,[L]),
   io:format("~p ~p ~p ~p ~n",[T1,T2,T3,T4]).

 函数说明：

＊add1 是最简单的实现，没有使用尾递归

＊add2 使用尾递归，最后没有reverse，结果是不正确的，仅仅用来比较

＊add3 使用尾递归

＊add4 使用list comprehension

 

在我的笔记本上运行，在N比较小(N<100000)的情况下，add3几乎总是比add1快，但是N比较大（N>100000）的时候，add1经常比add3快，说明lists:reverse的消耗还是挺大的

 

这个场景说明了几个问题：

＊在list比较大的时候，reverse操作消耗还是很大的（废话）

＊erlang的编译器会对类似add1的情况做优化，如果没有优化的话，应该会死的很惨

＊当使用尾递归会带来额外的事情的时候，需要权衡一下，是否应该选用

＊如果能事先知道程序运行的场景（这里是N的大小），写出来的程序性能才能更好

 

似乎都是废话，仅当记录。

评论

3 楼 mryufeng 2009-07-09  

Wrangler 会专门对这个进行重构 那说明Add3是最佳实践。

2 楼 cryolite 2009-07-09  

add1要省内存，尾递归的那个耗内存比较大

1 楼 argan 2009-07-08  

果然：
It is one of the principal Myths of Erlang Performance† that tail recursion is much more efficient than direct recursion in Erlang. Perhaps this was true in the early days of the language, but  optimizations applied between releases 7 and 12 have meant that it’s no longer true that tail recursion will give you a more efficient program.

The advice of the developers of the system is “The choice is now mostly
a matter of taste. If you really do need the utmost speed, you must
measure. You can no longer be absolutely sure that a tail-recursive func
tion will be the fastest in all circumstances.”