尾递归

Question

我正在实现以下函数：

void Add(list* node)
{
    if(this->next == NULL)
        this->next = node;
    else
        this->next->Add(node);
}

看起来在递归的每一步中都将进行尾调用Add。
我也可以这样实现：

void Add(list *node)
{
    list *curr = this;
    while(curr->next != NULL) curr = curr->next;
    curr->next = node;
}

这将完全不使用递归。
哪个版本更好？（在堆栈大小或速度方面）
请不要提供“为什么不使用STL / Boost /任何其他东西？”的评论/答案。

- Daniel

---

这基本上就是递归和迭代的对比吗？ - flight

@quasiverse，这是尾递归与迭代的比较（两者之间有很大的区别）。 - Daniel

如果你避免使用递归，那么你的堆栈就不会疯狂增长，但是过去20年中任何一个半靠谱的编译器都应该能够明智地处理尾递归。 - Flexo

Answer 1

他们在性能方面可能是相同的，因为编译器可能会将它们优化成完全相同的代码。

然而，如果您使用调试设置进行编译，编译器将不会针对尾递归进行优化，因此如果列表足够长，您可能会遇到堆栈溢出。还有一种（非常小的）可能性，即一个糟糕的编译器不会将递归版本优化为尾递归。在迭代版本中没有这样的风险。

选择哪个更清晰、更易于维护的版本，同时考虑到可能存在的非优化情况。

- Seth Carnegie

Answer 2

我尝试了一下，创建了三个文件来测试你的代码:

node.hh:

struct list {
  list *next;
  void Add(list *);
};

tail.cc:

#include "node.hh"

void list::Add(list* node)
{
    if(!this->next)
        this->next = node;
    else
        this->next->Add(node);
}

loop.cc:

#include "node.hh"

void list::Add(list *node)
{
    list *curr = this;
    while(curr->next) curr = curr->next;
    curr->next = node;
}

使用G++ 4.3编译了两个IA32文件，使用-O3和-S选项生成汇编输出而不是目标文件。

结果：

tail.s：

_ZN4list3AddEPS_:
.LFB0:
        .cfi_startproc
        .cfi_personality 0x0,__gxx_personality_v0
        pushl   %ebp
        .cfi_def_cfa_offset 8
        movl    %esp, %ebp
        .cfi_offset 5, -8
        .cfi_def_cfa_register 5
        movl    8(%ebp), %eax
        .p2align 4,,7
        .p2align 3
.L2:
        movl    %eax, %edx
        movl    (%eax), %eax
        testl   %eax, %eax
        jne     .L2
        movl    12(%ebp), %eax
        movl    %eax, (%edx)
        popl    %ebp
        ret
        .cfi_endproc

loop.s:

_ZN4list3AddEPS_:
.LFB0:
        .cfi_startproc
        .cfi_personality 0x0,__gxx_personality_v0
        pushl   %ebp
        .cfi_def_cfa_offset 8
        movl    %esp, %ebp
        .cfi_offset 5, -8
        .cfi_def_cfa_register 5
        movl    8(%ebp), %edx
        jmp     .L3
        .p2align 4,,7
        .p2align 3
.L6:
        movl    %eax, %edx
.L3:
        movl    (%edx), %eax
        testl   %eax, %eax
        jne     .L6
        movl    12(%ebp), %eax
        movl    %eax, (%edx)
        popl    %ebp
        ret
        .cfi_endproc

结论：输出非常相似（核心循环/递归在两者中变为movl，movl，testl，jne），所以真的不值得担心。递归版本少了一个无条件跳转，尽管我不想打赌哪个更快，如果有可测量性的话，则选择最自然的表达算法。即使您后来决定这是一个错误的选择，切换也不太困难。

将-g添加到编译中对使用g++的实际实现没有影响，尽管设置断点不再像您期望的那样工作-在我的GDB测试中，尾调用行上的断点最多被击中一次（但对于1个元素列表根本不会被击中） ，无论递归深度有多深。

时间记录：

出于好奇，我使用相同的g ++变体运行了一些计时。

#include <cstring>
#include "node.hh"

static const unsigned int size = 2048;
static const unsigned int count = 10000;

int main() {
   list nodes[size];
   for (unsigned int i = 0; i < count; ++i) {
      std::memset(nodes, 0, sizeof(nodes));
      for (unsigned int j = 1; j < size; ++j) {
        nodes[0].Add(&nodes[j]);
      }
   }
}

这个程序在循环和尾调用版本中分别运行了200次。结果在这个编译器和平台上是比较明显的。尾调用的平均值为40.52秒，而循环的平均值为66.93秒（标准差分别为0.45和0.47）。图表显示了结果的箱线图。

因此，如果尾调用递归看起来更好地表达了算法，我肯定不会害怕使用它，但我也不会刻意使用它，因为我怀疑这些时间观察结果可能会因平台/编译器版本而异。

- Flexo