问C++中的尾递归

EN

C++中的尾部递归看起来与C或任何其他语言相同。

void countdown( int count ) {
    if ( count ) return countdown( count - 1 );
}

尾递归(和一般的尾部调用)需要在执行尾部调用之前清除调用者的堆栈框架。对于程序员来说，尾递归类似于循环，return简化为像goto first_line;一样工作。但是，编译器需要检测你在做什么，如果它没有检测到，仍然会有一个额外的堆栈框架。大多数编译器都支持它，但是编写循环或goto通常更容易，风险也更小。

非递归尾调用可以启用随机分支(就像goto到其他函数的第一行)，这是一种更独特的工具。

请注意，在C++中，在return语句的作用域中不能有任何具有非平凡析构函数的对象。函数结束清理将要求被调用者返回到调用者，从而消除尾部调用。

还要注意(在任何语言中)，尾递归要求算法的整个状态在每一步都通过函数参数列表传递。(这一点很明显，因为要求在下一次调用开始…之前消除函数的堆栈框架您不能将任何数据保存在局部变量中。)此外，在函数返回尾部之前，不能对函数的返回值应用任何操作。

int factorial( int n, int acc = 1 ) {
    if ( n == 0 ) return acc;
    else return factorial( n-1, acc * n );
}

Wikipedia has a decent article on tail recursion。基本上，尾递归比常规递归更好，因为将其优化为迭代循环很简单，而且迭代循环通常比递归函数调用更有效。这在没有循环的函数式语言中尤其重要。

对于C++，如果您可以使用尾递归编写递归循环，这仍然很好，因为它们可以进行更好的优化，但在这种情况下，您通常可以在一开始就迭代地进行，因此收益不像在函数式语言中那么大。