CODEWITHSUNDEEP
performancerecursiontail-recursion
AbdullahC
AbdullahC

Reputation: 6730

Are tail-recursive functions ALWAYS to be avoided?

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?

Upvotes: 4

Views: 1224

Answers (4)

Mike Tunnicliffe
Mike Tunnicliffe

Reputation: 10762

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.

Upvotes: 6

Alex Humphrey
Alex Humphrey

Reputation: 6209

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.

Upvotes: 2

nos
nos

Reputation: 229058

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

Upvotes: 6

Konrad Garus
Konrad Garus

Reputation: 54005

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

Upvotes: 1

Related Questions