Iteration over lists

Richard Carlsson richardc@REDACTED
Fri Mar 17 17:57:29 CET 2006


Bjorn Gustavsson wrote:
> What you call recursion is in fact iteration expressed as tail-recursion.
> Naturally it is faster.
> 
> Real recursion would look this:
> 
> recursion([H | T]) ->
>     [integer_to_list(H) | recursion(T)];
> recursion([]) -> [].
> 
> A list comprehension will in fact be translated to the exact same
> code a the function above.
> [...]
>
> Using tail-recursion and then reversing is somewhat slower than either
> recursion or list comprehensions. My list size was 6000. I expect that
> if the lists are really huge, revrecursion will win.

Also, if each iteration does more work than just calling
integer_to_list, recursing, and consing up a new element,
it could make the stack frame size bigger, which could
significantly lower the break-even point in favour of the
tail recursive version with reverse at the end.

(This is of course assuming that the Beam compiler does not
use stack trimming techniques, but I don't think it does.)

It could be worth including such an example in the benchmarks.

	/Richard "too lazy to do my own measurements" C.



More information about the erlang-questions mailing list