通过一个求和(0~N)程序来对比Erlang的递归和尾递归效率并加深对尾递归的理解。

递归

#! /usr/bin/env escript

main([A]) ->
    N = list_to_integer(A),
    io:format("sum 0 - ~w = ~w~n",[N, sum(N)]).


sum(1) -> 1;

sum(N) -> N + sum(N-1).

尾递归

#! /usr/bin/env escript

main([A]) ->
    N = list_to_integer(A),
    io:format("sum 0 - ~w = ~w~n",[N, sum(N)]).


sum(N) -> sum(N, 0).

sum(0, N) -> N;
sum(M, N) -> sum(M-1, N+M).

对比

执行 0 ~ 1000000求和表现 (时间 & 内存消耗):

dingkaideMacBook-Pro:erlang dingkai$ time ./sum 1000000
sum 0 - 1000000 = 500000500000

real    0m4.261s
user    0m3.156s
sys 0m0.775s
内存消耗约为600MB

dingkaideMacBook-Pro:erlang dingkai$ time ./sum_tail 1000000
sum 0 - 1000000 = 500000500000

real    0m2.677s
user    0m2.493s
sys 0m0.177s
内存消耗约为16MB

总结

尾递归函数就是在递归调用前不累计任何未决运算的函数。如果函数子句中函数体的最后一个表达式是对自身的调用或者是个常数,那么它就是尾递归子句。如果一个函数的所有子句都是尾递归子句,那么它就是一个尾递归函数。