# Tail Recursion

Posted in programming -

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().
[{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().
[{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) ->
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.