谁能用C++给我演示一个简单的尾递归函数?
为什么尾递归更好,如果它是的话?
除了尾递归之外,还有其他类型的递归吗?
发布于 2010-04-23 03:13:17
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 );
}
发布于 2010-04-23 03:16:18
Wikipedia has a decent article on tail recursion。基本上,尾递归比常规递归更好,因为将其优化为迭代循环很简单,而且迭代循环通常比递归函数调用更有效。这在没有循环的函数式语言中尤其重要。
对于C++,如果您可以使用尾递归编写递归循环,这仍然很好,因为它们可以进行更好的优化,但在这种情况下,您通常可以在一开始就迭代地进行,因此收益不像在函数式语言中那么大。
https://stackoverflow.com/questions/2693683
复制相似问题