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

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 2

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