Recursion

[Heinz Eriksson]

Fredrik Linder wrote:
> 
> [Clip from: "lists:zip / zip_with / unzip etc"]
> >
> > Would this be ok to you then:
> >
> > ziph([H1|L1],[H2|L2], Z) ->
> >     [{H1,H2}|ziph(L1,L2,Z)];
> > ziph([],[], Z) ->
> >     Z.
> >
> > zip(A,B) ->
> >     ziph(A,B,[]).
> >
> > ?
> > Is that tail recursive?
> 
> No, it is not tail-recursive, sorry. One can see that 'cause there is
> something to do after the recursive call, i.e the creation of a cons cell.

Ok, thank you, then everything fits my previous 'understanding'.

Thomas wrote.
>No, this makes no sense. You don't use the last argument!

Yes I do, the messed up non-tail recursive variant with the
dragged along empty list argument is actually used when 
recursion terminates:-)

> 
> 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).

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.


/hz