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

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 2

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 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

A similar optimization that separates program text function calls from implementation function calls is 'inlining'. In modern/thoughtful languages function calls have little relation to machine level function calls.

Answer 5

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...)

Answer 6

It might help if you try to think of tail recursion as being the equivalent of iteration.

Tail recursion is not recursion in the same sense as you would have in something like C, where each call causes more stuff to be pushed on to the stack. In tail recursion each time a call is made nothing is pushed to the stack.

In the case of Erlang what this means is that all the variables are unbound and a fresh call is made to the function with the new arguments. The original return point is preserved so when you hit your boundary condition then the function returns, but doesn't have to unwind layer upon layer of info from the stack.

As previous posters have said, the actual implementation of tail recursion inside the Erlang is of course more complicated than that, with tail-call optimization going on. But since you're not working with the assembler code you generally don't need to worry about how that works.