03月10, 2010

erlang的尾递归优化

  1. 计算 f(n) = f(n-1)+f(n-2)+f(n-3)
  2. 倒序列表L

树形递归:

foo(N) when N < 3 ->
        N;
foo(N) ->
        foo(N - 1) + foo(N - 2) + foo(N - 3).

线性迭代(尾递归优化):

foo(N) when N < 3 ->
        N;
foo(N) ->
        foo_iter(0,1,2,N-3).

foo_iter(A,B,C,0) ->
        A + B + C;
foo_iter(A,B,C,Count) ->
        foo_iter(B, C, A + B + C, Count - 1).

线性递归

range(N) when N=:=0 ->
        [];
range(N) ->
        [N-1|range(N-1)].

线性迭代(尾递归)

revc(L) ->
        revc_iter([],L).

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

有兴趣的同学可以测一下,效率可不是差一个两个数量级的~

本文链接:https://www.h5jun.com/post/尾递归优化.html

-- EOF --

Comments