尾调用递归

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/what？" 意见/答案.

Answer 1

它们可能在性能上是相同的,因为编译器可能会将它们优化为完全相同的代码.

但是,如果在Debug设置上进行编译,编译器将不会针对尾部递归进行优化,因此如果列表足够长,则可能会出现堆栈溢出.还有(非常小的)可能性,错误的编译器不会优化尾递归的递归版本.在迭代版本中没有风险.

选择哪一个更清晰,更容易保持考虑非优化的可能性.

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

所以我当然不会害怕使用尾调用递归,如果它似乎是表达算法的更好方式,但我可能也不会忘记使用它,因为我怀疑这些时序观察最有可能与平台/编译器(版本)不同.