c++ - 这是否符合尾递归的条件？

Question

Possible Duplicate:
Tail recursion in 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);
}

谢谢!

Answer 1

简而言之，在递归调用 (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)。之后，我们不需要将被调用函数的返回值用于其他任何事情，因此我们不需要返回到当前帧。因此，我们可以丢弃堆栈帧并应用其他优化。

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