[erlang-questions] about tail-recursive

Bjorn Gustavsson <>
Wed Apr 16 11:27:48 CEST 2008


"É¢Î" <> writes:

> Hi everyone.
> Recently I read http://www.erlang.org/download/armstrong_thesis_2003.pdf.
>  In this paper 3.3.8, the author talk about tail-recursive:
> "Firstly the non tail-recursive way:
> factorial(0) -> 1;
> factorial(N) -> N * factorial(N-1).
> "
> I see this section is non tail-recursive. In my mind, the tail-recursive is
> the better, because it do not consuming stack!

Yes, it is.

> When I read OTP src, I find in the stdlib lists.erl. the map/2 write in this
> style:
> "map(F, [H|T]) ->
>     [F(H)|map(F, T)];
> map(F, []) when is_function(F, 1) -> [].

Correct! It is not tail-recursive.

The tail-recursive version would not consume any stack, but it would have to
build a list in reverse order, which it would have to reverse by calling lists:reverse/1.
The stack space and the list consumes exactly the same amount of memory (in R12B).

See

http://www.erlang.org/doc/efficiency_guide/myths.html#2.3

/Bjorn
-- 
Björn Gustavsson, Erlang/OTP, Ericsson AB



More information about the erlang-questions mailing list