How to do list concatenation "the correct" way (using tail-recursion)

Question

I'm working on the following Erlang exercise:

Write a function that, given a list of lists, will concatenate them. Example:

concatenate([[1,2,3], [], [4,five]]) ⇒ [1,2,3,4,five].

And I came up with this:

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate([T|Tail])].

Which works, but I noticed that I'm doing this [T|Tail] thing.

First question

Is this still considered direct recursion?

After that, I got rid of that [T|Tail] and used an accumulator instead (like below).

Second question

Is now the second code considered tail recursion?

The book hints to the use of a helper function (which the second code is doing), but it seems quite verbose. Is it because I'm missing something?

concatenate([]) ->
    [];
concatenate([[H]|Tail]) ->
    [H|concatenate(Tail)];
concatenate([[]|Tail]) ->
    concatenate(Tail);
concatenate([[H|T]|Tail]) ->
    [H|concatenate(T,Tail)].

concatenate([],Tail) ->
    concatenate(Tail);
concatenate([H],Tail) ->
    [H|concatenate(Tail)];
concatenate([H|T],Tail) ->
    [H|concatenate(T,Tail)].

Answer 1

As @Yasir explained neither are tail-recursive, but I wouldn't worry that much about it (see below). Using a helper function can improve the code by eliminating the partial rebuilding of the input list. Your code is a little verbose and can be simplified by removing some unnecessary clauses in conc/1 and always calling conc/2 instead:

conc([H|T]) -> conc(H, T);
conc([]) -> [].

conc([H|T], Rest) -> [H|conc(T, Rest)];
conc([], Rest) -> conc(rest).

Splitting the tail-recursive version with an accumulator would then become:

conc(List) -> conc(List, []).

conc([H|T], Acc) -> conc(H, T, Acc);
conc([], Acc) -> lists:reverse(Acc).

conc([H|T], Rest, Acc) -> conc(T, Rest, [H|Acc]);
conc([], Rest, Acc) -> conc(Rest, Acc).

Now, the difference in speed is much less these days than it used to be, see Myth: Tail-recursive functions are MUCH faster than recursive functions, so it is best to use the style which seems clearer. I personally prefer not to use an accumulator unless I have to.

Answer 2

Both [H|concatenate([T|Tail])] and [H|concatenate(T,Tail)] are not tail-recursive calls, because either calls are a part of another expression, and thus control would be returned to the expression, which includes a call to your concatenate/1,2.

The proper tail-recursive conc could look something like:

-module(concat).
-export([concatenate/1]).

concatenate(L) ->
     conc(L, []).

conc([], Acc) ->
     lists:reverse(Acc);
conc([[H|T] | L1], Acc)->
     conc([T|L1], [H|Acc]);
conc([[] | L1], Acc) ->
     conc(L1, Acc).

Here, in conc/2, the call to itself is the last operation in the function body, and the function will never return.

EDIT: If we forget about optimizations of non-tail-recursive calls, @Robert mentioned, for the moment, we could end up with memory overflow due to return adresses of calling functions passed onto the stack (heap?). This could happen if you called your non-tail-recursive function passing it a list with a considerable length on a system with insufficient memory size to hold such amount of return addresses.