Recursion

Fredrik Linder fredrik.linder@REDACTED
Sun Jul 7 16:46:21 CEST 2002


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

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.

This is non-tail-recursive:

zip([H1 | T1], [H2 | T2]) -> [{H1, H2} |  zip(T1, T2)];
zip([], []) -> [].

Btw, in this case there is no need to name the helper function differently
than the function it helps (different number of arguments). They do the same
thing, except setting the default accumulator value, so then it is good
practice to give them the same name.

/Fredrik




More information about the erlang-questions mailing list