Tail recursion in Erlang

Question

Hi,

I am really struggling to understand tail recursion in Erlang.

I have the following eunit test:

db_write_many_test() ->
    Db = db:new(),
    Db1 = db:write(francesco, london, Db),
    Db2 = db:write(lelle, stockholm, Db1),
    ?assertEqual([{lelle, stockholm},{francesco, london}], Db2).

And here is my implementation:

-module(db) .
-include_lib("eunit/include/eunit.hrl").
-export([new/0,write/3]).

new() ->
    [].

write(Key, Value, Database) ->
    Record = {Key, Value},
    [Record|append(Database)].

append([H|T]) ->
    [H|append(T)];  
append([])  ->
    [].

Is my implementation tail recursive and if not, how can I make it so?

Thanks in advance

Answer 1

Your implementation is not tail recursive because append must hold onto the head of the list while computing the tail. In order for a function to be tail-recursive the return value must not rely on an value other than the what is returned from the function call.

you could rewrite it like so:

append(Acc, []) -> %% termination;
    Acc;
append(Acc, [H|T]) ->
    Acc2 = Acc ++ dosomethingto(H); %% maybe you meant this to be your write function?
    append(Acc2, T); %% tail rercursive

Notice that all the work is finished once the tail recursive call occurs. So the append function can forget everthing in the function body and only needs to remember the values of the arguments it passes into the next call.

Also notice that I put the termination clause before the recursive clause. Erlang evaluates the clauses in order and since termination clauses are typically more specific the less specific recursive clauses will hide them thus preventing the function from ever returning, which is most likey not your desired behaviour.