Erlang: functions (part 2)

We know how to implement recursion, but it's often not enough to directly call a function from inside itself. Tail recursion is a functional programming idiom that lets functions recur on themselves for an unbound amount of times.

The stack

Let's take the definition of factorial from last week:

recursive_factorial(0) -> 1;
recursive_factorial(N) -> recursive_factorial(N - 1) * N.

We are recurring N times, where N is the number passed in the first call to recursive_factorial/1. Only when N is equal to 0 the first clause is matched and the recursion stops; afterwards, each call to recursive_factorial(0), recursive_factorial(1), ... returns and its result is multiplied for the argument N kept in memory until then.

You probably know that all function calls are piled up onto a stack, a data structure where the last inserted element is always the first to being pulled out. In the case of recursive_factorial/1, the stack looks like this:

factorial(0) -> % now I'll return 1
factorial(1) -> local: N = 1
factorial(2) -> local: N = 2
factorial(3) -> local: N = 3

when we are calculating recursive_factorial(3) and we are in recursive_factorial(0), of course.

The problem with this kind of recursion is that you may run out of stack space, *especially* if the function will continuously run and call itself, like a main loop. In C++, you could write:

while (1) {
    // wait for input, do something
}

but in Erlang doing the same with functions:

main() ->
    // wait for input, do something
    main().

would not be possible without tail recursion. The stack trace would grow every iteration, until we would run out of memory.

From direct recursion to tail recursion

The definition of a tail call in Erlang is:

The last statement of the execution of a function, whose return value becomes the return value of the original function.

For example, in:

a() ->
    b(),
    c().

c() is a tail call, while b() is not. If we wrote:

a(A) ->
    b(),
    A * c().

c() wouldn't be a tail call, because its return value would have to be processed to become a(A)'s return value.

When a tail call points to the function itself, it is an instance of tail recursion. Let's rewrite recursive_factorial:

tail_factorial(N) -> tail_factorial(1, N).

tail_factorial(N, 0) -> N;
tail_factorial(Result, N) -> tail_factorial(Result * N, N - 1).

simple_test() ->
    ?assertEqual(6, tail_factorial(3)),
    ?assertEqual(2, tail_factorial(2)),
    ?assertEqual(1, tail_factorial(1)),
    ?assertEqual(1, tail_factorial(0)).

We are using a Result variable, like we would do in a for() cycle:

for (int I = N; I > 0; I--) {
    Result = Result * I;
} // this is not Erlang code

When we call tail_factorial(3), the stack now looks like this:

factorial(6, 0) -> % now I'll return 6
factorial(6, 1) ->
factorial(3, 2) ->
factorial(1, 3) ->
factorial(3) ->

and we don't have local variables anymore. Since the return value is the same for all the functions, we can actually skip a few steps and introduce an optimization:

factorial(6, 0) -> % now I'll return 6
factorial(3) -> 

factorial(6, 0) will return directly its result to factorial(3). The tail recursive calls can overwrite the previous call to the same function in the stack, without anyone noticing.

So our main loop:

main() ->
    // wait for input, do something
    main().

now can actually work forever without exhausting the stack.

Note that for ordinary functions, with a bound number of recursive executions, tail recursion is not strictly necessary. Performance considerations must only be made after measuring two alternatives, and you shouldn't go for tail recursion just in all your functions for optimization reasons alone.

More examples, please

Let's implement the zip/2 function. It already exists in the lists module as lists:zip, but it is a good exercise for tail recursion.

This is what zip does:

    ?assertEqual([],
        zip([], [])),
    ?assertEqual([{a, 'alpha'}],
            zip([a], ['alpha'])),
    ?assertEqual([{a, 'alpha'}, {b, 'bravo'}, {c, 'charlie'}],
            zip([a, b, c], ['alpha', 'bravo', 'charlie'])).

Here's an implementation with tail recursion. We still have one accumulator variable, Result, but two arguments to pass around.

zip(First, Second) -> zip([], First, Second).

zip(Result, [], []) -> Result;
zip(Result, [FirstHead|FirstTail], [SecondHead|SecondTail]) ->
    zip(Result ++ [{FirstHead, SecondHead}], FirstTail, SecondTail).

By now you can see the pattern:

• the original function performs initialization.
• The function with the additional accumulator argument performs a step of iteration and relaunch itself.

Let's try a problem where the original function has to behave as a bridge. Calculating averages is tricky because you need both the size of a list and the sum of its contents.

average_test() ->
    ?assertEqual(2.0, average([2])),
    ?assertEqual(2.0, average([1, 3])),
    ?assertEqual(2.0, average([1, 3, 1, 1, 1, 5])).

Erlang has a length function, but let's build average/1 via tail recursion:

average(Numbers) ->
    {Total, Size} = average(0, 0, Numbers),
    Total / Size.

average(Total, Size, []) -> {Total, Size};
average(Total, Size, [Head|Tail]) ->
    average(Total + Head, Size + 1, Tail).

Conclusions

Tail recursion is a different way of implementing recursion - and it is optional in Erlang for implementing algorithms. However, it's mandatory when it comes to build cycles like a main/0 function.

All the code I wrote in this article is available at the Github repository for this series.