Recursion

[Fredrik Linder]

Sorry for my later reply, but I had a week vacation. :)

> > This is tail-recursive however:
> >
> > zip(L1, L2) ->
> >     zip(L1, L2, []).
> >
> > zip([H1 | T1], [H2 | T2], Acc) ->
> >     zip(T1, T2, [{H1, H2} | Acc]); % Nothing to be done after the
recursive
> > call
> > zip([], [], Acc) ->
> >     lists:reverse(Acc). % This is necesary if you want to keep the order
of
> > your list elements.
>
> That was close my initial attempt (except for the
> helper function naming) to which Thomas commented that:
>
> >This solution for zip has complexity 2N (2 times the length
> >of the list). It is easy to make a solution that only
> >traverses the list once.
>
> Does this imply something more than a space / time compromise
> for the function evaluation characteristics? (Except elegance
> of the implementation).

With my limited knowledge of the implementation of Erlang, I guess not,
except from the fact that lists always is created bottom-up (using
cons-cells), and hence forcing order-sensitive tail-recursive functions to
traverse lists at least twice.

With a simple test repeated 7 times, each time traversing 10000 lists with
1000 elements I got that the tail-recursive function actually was 4% faster
than the non-tail-recursive. (See attachment)

> Also:
> You order the clauses differently (than Thomas) for the non-tail
> recursive version. Which is to preferable? My guess was that placing
> the  zip([],[])->[]  last was best.

I think so too ;-) Maybe it no longer matters due to hopefully better
implementation of Erlang, but earlier I think it did. So placing the clauses
executed only once last could be a good micro-optimization.

/Fredrik
-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.erl
Type: application/octet-stream
Size: 589 bytes
Desc: not available
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20020717/71e01f5d/attachment.obj>