Tail Recursion

One of the cool things in Erlang is efficient tail recursion. It means that when a function calls itself as its last instruction, Erlang re-uses that stack frame. That probably doesn’t clarify it much, so let’s look at an example.

This Java code

public class Recursor {
    public static void main(String[] args) {
        System.out.println("Total: " + countdown(10));
    }

    private static int countdown(int x) {
        return countdown(x, 0);
    }

    private static int countdown(int x, int total) {
        if (0 == x) {
            return 1/0;  // GENERATE EXCEPTION
        }
        else {
            // recurse with decreased countdown and increased total
            return countdown(x - 1, total + 1);
        }
    }
}

generates this stacktrace

$ java Recursor
Exception in thread "main" java.lang.ArithmeticException: / by zero
 at Recursor.countdown(Recursor.java:12)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:15)
 at Recursor.countdown(Recursor.java:7)
 at Recursor.main(Recursor.java:3)

If the countdown had started at 100, you’d have a hundred lines in the stacktrace.

The equivalent code in Erlang

-module(recurse).

-export([countdown/0]).

countdown() ->
    countdown(10, 0).

countdown(0, Total) ->
    Total/0;  %% generate error
countdown(Val, Total) ->
    %% recurse with decreased countdown and increased total
    countdown(Val - 1, Total + 1).

generates this stacktrace

> catch recurse:countdown().     
{'EXIT',{badarith,[{recurse,countdown,2,
                            [{file,"recurse.erl"},{line,9}]},
                   {erl_eval,do_apply,6,[{file,"erl_eval.erl"},{line,573}]},
                   {erl_eval,expr,5,[{file,"erl_eval.erl"},{line,357}]},
                   {shell,exprs,7,[{file,"shell.erl"},{line,674}]},
                   {shell,eval_exprs,7,[{file,"shell.erl"},{line,629}]},
                   {shell,eval_loop,3,[{file,"shell.erl"},{line,614}]}]}}

Even though the function has called itself recursively ten times, it’s only one line of the stacktrace. (I’ve tested it up to 100 million.)

In fact, this is true of any tail call, even to different functions. This code generates the same stacktrace

countdown() ->
    countdown(100, 0).

countdown(0, Total) ->
    Total/0;
countdown(Val, Total) ->
    bounce_one(Val - 1, Total + 1).

bounce_one(Val, Total) ->
    bounce_two(Val, Total + 1).

bounce_two(Val, Total) ->
    countdown(Val, Total + 1).

Surprisingly, even non-tail recursion in Erlang is done fairly efficiently. This version of the code, where the last instruction is addition

countdown() ->
    countdown(10).

countdown(0) ->
    1/0;
countdown(Val) ->
    1 + countdown(Val - 1).

generates this stacktrace

> catch recurse:countdown().
{'EXIT',{badarith,[{recurse,countdown,1,
                            [{file,"recurse.erl"},{line,9}]},
                   {recurse,countdown,1,[{file,"recurse.erl"},{line,11}]},
                   {recurse,countdown,1,[{file,"recurse.erl"},{line,11}]},
                   {erl_eval,do_apply,6,[{file,"erl_eval.erl"},{line,573}]},
                   {erl_eval,expr,5,[{file,"erl_eval.erl"},{line,357}]},
                   {shell,exprs,7,[{file,"shell.erl"},{line,674}]},
                   {shell,eval_exprs,7,[{file,"shell.erl"},{line,629}]},
                   {shell,eval_loop,3,[{file,"shell.erl"},{line,614}]}]}}

Even there, there are only three stack frames for that recursive function. (It’s the same even with a recursion depth of 100.) I’ll have to find a real Erlang expert to explain that.

The reason this is important is that it’s the basis for the Actor model in Erlang. Actors are long-running processes that fundamentally look something like

loop(State) ->
    receive Message ->
        NewState = handle_message(Message, State),
        loop(NewState)
    end.

They wait for incoming messages, do something with them, and recurse with their updated state. Yes, you could do that in Java with a while loop, but doing it with a recursive function has two benefits. The first is just cleanliness: When you call a function, it just gets the values that are passed to it. In a while loop, you have to worry about the state of any variables that are visible from inside it.

The big win is that this is what lets Erlang do hot code loading. All of the process state gets passed as a parameter, so its data is separate from its code. When loop calls itself, it can invoke the new version of its code. Because Java classes combine code and data, you can’t update the processing logic without wiping out the application state.