2

可能重复：
C++ 中的尾递归

我是 C++ 中尾递归的新手。我的项目要求我使所有函数尾递归。我已经测试了以下代码，它可以正常工作。但是，我不确定我的做法是否符合尾递归的要求。

static int sum_helper(list_t hList, int accumulator){
    if (list_isEmpty(hList))
        return accumulator;
    else {
        accumulator += list_first(hList);
        hList = list_rest(hList);
        return sum_helper(hList, accumulator); 
    }
}

int sum(list_t list){
/* 
 // EFFECTS: returns the sum of each element in list
 //          zero if the list is empty.
 */
    if (list_isEmpty(list))
        return 0;
    return sum_helper(list, 0);
}

谢谢！

4

3 回答 3

2

如果 list_t 没有重要的析构函数，它就是尾递归。如果它确实有一个非平凡的析构函数，则析构函数需要在递归调用返回之后和函数本身返回之前运行。

奖金：

int sum(list_t hList, int accumulator = 0) {
return list_isEmpty(hList)
    ? 0
    : sum(list_rest(hList), accumulator + list_first(hList));
}

但口味各不相同；有些人可能更喜欢你的。

于 2012-09-23T23:14:16.070 回答
2

简而言之，在递归调用 ( sum_helper) 之后你什么也不做。这意味着您永远不需要返回给调用者，因此，您可以丢弃调用者的堆栈帧。

以正态阶乘函数为例

int fact(int x)
{
    if(x == 0)
        return 1;
    else
        return x * fact(x-1);
}

这不是尾递归，因为fact(x-1)需要返回 的值，然后乘以 6。相反，我们可以稍微作弊，也可以通过一个累加器。看到这个：

int fact(int x, int acc)
{
     if(x == 0)
         return acc;      // Technically, acc * 1, but that's the identity anyway.
     else
         return fact(x-1, acc*x);
}

在这里，控制流中的最后一个函数调用是fact(x-1, acc*x). 之后，我们不需要将被调用函数的任何返回值用于其他任何事情，因此我们不需要返回到当前帧。出于这个原因，我们可以丢弃堆栈帧并应用其他优化。

免责声明：我可能错误地应用了阶乘算法，但你明白了。希望。

于 2012-09-23T23:09:25.560 回答
1

从理论上讲，是的，它是尾递归（前提是 hList 没有非平凡的析构函数）。但从实践的角度来看，这取决于您的编译器及其设置。让我们看一下为这个简单代码生成的程序集：

#include <cstdlib>

struct list{
   int head;
   list * tail;
};


int sum_helper(list * l, int accumulator){
    if (l == NULL)
        return accumulator;
    else {
        accumulator += l->head;
        return sum_helper(l->tail, accumulator); 
    }
}

优化：（g++ -O2 ...，省略了无聊的部分）：

    testq   %rdi, %rdi
    movl    %esi, %eax
    je  .L2
    ...
.L6:
    ...
    jne .L6                  <-- loop
.L2:
    rep
    ret

这显然是一个循环。但是当你禁用优化时，你会得到：

_Z10sum_helperP4listi:
.LFB6:
    ...
    jne .L2
    movl    -12(%rbp), %eax
    jmp .L3
.L2:
    ...
    call    _Z10sum_helperP4listi     <-- recursion
.L3:
    leave
    .cfi_def_cfa 7, 8
    ret

这是递归的。

于 2012-09-23T23:26:32.700 回答