Home > Uncategorized > erlang的尾递归优化

erlang的尾递归优化

March 10th, 2010
Goto comments Leave a comment

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

树形递归：

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

线性迭代（尾递归优化）：

  1. foo(N) when N < 3 ->
  2.         N;
  3. foo(N) ->
  4.         foo_iter(0,1,2,N-3).
  5.  
  6. foo_iter(A,B,C,0) ->
  7.         A + B + C;
  8. foo_iter(A,B,C,Count) ->
  9.         foo_iter(B, C, A + B + C, Count - 1).

线性递归

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

线性迭代（尾递归）

  1. revc(L) ->
  2.         revc_iter([],L).
  3.  
  4. revc_iter(T, []) ->
  5.         T;
  6. revc_iter(T,[H|L]) ->
  7.         revc_iter([H|T],L).

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

月影 Uncategorized

  1. No comments yet.