Tail/Non tail recursion

Luke Gorrie luke@REDACTED
Thu Aug 28 15:08:23 CEST 2003


Jilani Khaldi wrote:
> Hi All,
> Is there a better way to write this code when there is a lot of
> elements in the list?
> square([H|T]) -> [(H*H|square(T)];
> square([]) -> [].

Short answer: That's best in that it uses time and space proportional
to the length of the list, just like lists:map, list comprehension,
etc.

Long answer:

There was an eye-wateringly detailed look at the performance of
various implementations of roughly this algorithm on this list two
years ago: tail recursion + reverse, continuation-passing style,
etc. I don't know if the conclusions are still accurate for R9C, but
here's the start of the thread if anyone is interested:
http://www.erlang.org/ml-archive/erlang-questions/200110/msg00019.html
And the conclusion:
http://www.erlang.org/ml-archive/erlang-questions/200110/msg00024.html

P.S., I like: square(L) -> [N*N || N <- L].

-Luke




More information about the erlang-questions mailing list