总是要避免尾递归函数吗？

Question

如果我没记错的话,尾递归函数总是有一个简单的非递归等价.由于递归涉及不必要的函数调用开销,因此最好以非递归方式进行.

这种假设总是如此吗？是否还有其他参数支持/反对尾递归？

Answer 1

如果您正在使用具有良好编译器的语言,那么可以优化这些类型的递归,因此在这些情况下如果它提高了使用递归的可读性,我会说要坚持使用它.

Answer 2

不,并非总是如此.许多语言和/或编译器可以轻松地优化尾递归调用,并将其重写为迭代版本,或者以某种方式重用堆栈帧以用于后续调用.

Scheme语言要求实现采用尾调用优化

gcc也可以优化尾调用,考虑一个释放链表中所有节点的函数:

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

编译,优化:

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

也就是说,一个简单的跳转而不是递归调用free_all