performance - 是否总是要避免尾递归函数？

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

Answer 3

不。

追求可读性。许多计算可以更好地表示为递归（尾或其他）函数。避免它们的唯一其他原因是，如果您的编译器没有进行尾调用优化，并且您希望您可能会破坏调用堆栈。

Answer 4

这取决于语言，但通常开销并不大。它可能是主观的，但递归函数往往更容易理解。大多数情况下，您不会注意到性能差异。

我会选择尾递归，除非我的平台非常不擅长处理它（即根本不这样做，但总是推入堆栈）。