Are tail-recursive functions ALWAYS to be avoided?

Question

If I recall correctly, tail recursive functions always have an easy non-recursive equivalent. Since recursion involves unnecessary function call overhead, it's better to do it the non-recursive way.

Is this assumption always true? Are there any other arguments for/against tail-recursion?

Answer 1

No, it's not always true. Many languages and/or compilers can easily optimize a tail recursive call , and rewrite it to an iterative version, or in some way reuse the stack frame for subsequent calls.

The Scheme language mandates that implementation employ tail call optimization

gcc can optimize tail calls as well, consider a function for freeing all the nodes in a linked list:

void free_all(struct node *n)
{
    if(n != NULL) {
        struct node *next = n->next;
        free(n);
        free_all(next);
    }
}

compiles to, with optimization:

free_all:
        pushl   %ebp
        movl    %esp, %ebp
        pushl   %ebx
        subl    $20, %esp
        movl    8(%ebp), %eax
        testl   %eax, %eax
        je      .L4
        .p2align 4,,7
        .p2align 3
.L5:
        movl    4(%eax), %ebx
        movl    %eax, (%esp)
        call    free
        testl   %ebx, %ebx
        movl    %ebx, %eax
        jne     .L5
.L4:
        addl    $20, %esp
        popl    %ebx
        popl    %ebp
        ret

That is, a simple jump instead of recursivly calling free_all

Answer 2

If you are using a language with a good compiler then these types of recursion can be optimised away, so in those cases if it improves readability to use recursion, I'd say to stick with it.

Answer 3

No.

Go for readability. Many computations are better expressed as recursive (tail or otherwise) functions. The only other reason to avoid them would be if your compiler does not do tail call optimizations and you expect you might blow the call stack.

Answer 4

It depends on language, but often the overhead isn't that big. It may be subjective, but recursive functions tend be much easier to comprehend. Most of the time you wouldn't notice the performance difference.

I would go for tail recursion unless my platform was very bad at dealing with it (i.e. not doing it at all, but always pushing onto stack).