Does using a lot of tail-recursion in Erlang slow it down?

Question

I've been reading about Erlang lately and how tail-recursion is so heavily used, due to the difficulty of using iterative loops.

Doesn't this high use of recursion slow it down, what with all the function calls and the effect they have on the stack? Or does the tail recursion negate most of this?

Answer 1

The point is that Erlang optimizes tail calls (not only recursion). Optimizing tail calls is quite simple: if the return value is computed by a call to another function, then this other function is not just put on the function call stack on top of the calling function, but instead the stack frame of the current function is replaced by one of the called function. This means that tail calls don't add to the stack size.

So, no, using tail recursion doesn't slow Erlang down, nor does it pose a risk of stack overflow.

With tail call optimization in place, you can not only use simple tail recursion, but also mutual tail recursion of several functions (a tail-calls b, which tail-calls c, which tail-calls a ...). This can sometimes be a good model of computation.

Answer 2

Iterative tail recursion is generally implemented using Tail calls. This is basically a transformation of a recursive call to a simple loop.

C# example:

uint FactorialAccum(uint n, uint accum) {
    if(n < 2) return accum;
    return FactorialAccum(n - 1, n * accum);
};
uint Factorial(uint n) {
    return FactorialAccum(n, 1);
};

to

uint FactorialAccum(uint n, uint accum) {
start:
    if(n < 2) return accum;
    accum *= n;
    n -= 1;
goto start;
};
uint Factorial(uint n) {
    return FactorialAccum(n, 1);
};

or even better:

uint Factorial(uint n) {
    uint accum = 1;
start:
    if(n < 2) return accum;
    accum *= n;
    n -= 1;
goto start;
};

---

C# not real tail recursion, this is because the return value is modified, most compilers won't break this down into a loop:

int Power(int number, uint power) {
    if(power == 0) return 1;
    if(power == 1) return number;
    return number * Power(number, --power);
}

to

int Power(int number, uint power) {
    int result = number;
start:
    if(power == 0) return 1;
    if(power == 1) return number;
    result *= number;
    power--;
goto start;
}

Answer 3

It should not affect performance in most cases. What you're looking for is not just tail calls, but tail call optimization (or tail call elimination). Tail call optimization is a compiler or runtime technique that figures out when a call to a function is the equivalent of 'popping the stack' to get back to the proper function instead of just returning. Generally tail call optimization of can only be done when the recursive call is the last operation in the function, so you have to be careful.

Answer 4

There is a problem pertaining to tail-recursion but it is not related to performance - Erlang tail-recursion optimisation also involves elimination of the stack trace for debugging.

For instance see Point 9.13 of the Erlang FAQ:

Why doesn't the stack backtrace show the right functions for this code:

-module(erl).
-export([a/0]).

a() -> b().
b() -> c().
c() -> 3 = 4.           %% will cause badmatch

The stack backtrace only shows function c(), rather than a(), b() and c(). This is because of last-call-optimisation; the compiler knows it does not need to generate a stack frame for a() or b() because the last thing it did was call another function, hence the stack frame does not appear in the stack backtrace.

This can be a bit of pain when you hit a crash (but it does kinda go with the territory of functional programming...)