C ++中的尾递归
有人能告诉我一个简单的C ++尾递归函数吗？
为什么尾部递归更好，如果它甚至是？
除了尾递归之外还有什么其他类型的递归？
一个简单的尾部递归函数：
unsigned int f( unsigned int a ) {
if ( a == 0 ) {
return a;
}
return f( a - 1 ); // tail recursion
}
尾递归基本上是当：
并不是“更好”，除非一个好的编译器可以移除递归，将其转换为循环。 这可能会更快，并且肯定会节省堆栈使用量。 GCC编译器可以做这个优化。
C ++中的尾部清除看起来与C或任何其他语言相同。
void countdown( int count ) {
if ( count ) return countdown( count - 1 );
}
尾递归（通常是尾调用）需要在执行尾调用之前清除调用者的栈帧。 对于程序员来说，尾递归类似于一个循环， return减少到像goto first_line;一样工作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 );
}
尾递归是尾调用的特例。 尾部调用是编译器可以看到从被调用函数返回时不需要执行的操作 - 从本质上将被调用函数的返回值转换为它自己的值。 编译器通常可以执行一些堆栈修复操作，然后跳转（而不是调用）到被调用函数第一条指令的地址 。
除了消除一些回调电话之外，关于此的一个重要的事情是您还减少了堆栈使用情况。 在某些平台或操作系统代码中，堆栈可能非常有限，并且在高级计算机上，例如桌面系统中的x86 CPU，会降低堆栈使用率，这样可以提高数据高速缓存的性能。
尾递归是被调用函数与调用函数相同的地方。 这可以变成循环，这与上面提到的尾部呼叫优化中的跳转完全相同。 由于这是相同的功能（被调用者和调用者），所以在跳转之前需要完成的堆栈修正较少。
以下显示了一种执行递归调用的常见方法，这对于编译器变成循环更加困难：
int sum(int a[], unsigned len) {
if (len==0) {
return 0;
}
return a[0] + sum(a+1,len-1);
}
这非常简单，许多编译器可能无论如何都可以解决它，但正如你所看到的，在被调用的和返回一个数字之后还有一个额外的事情需要发生，所以简单的尾部调用优化是不可能的。
如果你这样做了：
static int sum_helper(int acc, unsigned len, int a[]) {
if (len == 0) {
return acc;
}
return sum_helper(acc+a[0], len-1, a+1);
}
int sum(int a[], unsigned len) {
return sum_helper(0, len, a);
}
您将能够利用这两个功能中的呼叫作为尾呼叫。 这里sum函数的主要工作是移动一个值并清除寄存器或堆栈位置。 sum_helper完成所有的数学运算。
既然你在你的问题中提到了C ++，我会提一些关于它的特别的东西。 C ++隐藏了C没有的东西。 在这些析构函数中，最主要的是会影响尾部调用优化。
int boo(yin * x, yang *y) {
dharma z = x->foo() + y->bar();
return z.baz();
}
在这个例子中，对baz的调用并不是一个真正的尾巴调用，因为z需要在从baz返回之后被破坏。 我相信，即使在调用期间不需要变量的情况下，C ++规则可能会使优化更加困难，例如：
int boo(yin * x, yang *y) {
dharma z = x->foo() + y->bar();
int u = z.baz();
return qwerty(u);
}
在qwerty返回之后，z可能不得不被销毁。
另一件事是隐式类型转换，它也可以在C中发生，但在C ++中可能更复杂和常见。 例如：
static double sum_helper(double acc, unsigned len, double a[]) {
if (len == 0) {
return acc;
}
return sum_helper(acc+a[0], len-1, a+1);
}
int sum(double a[], unsigned len) {
return sum_helper(0.0, len, a);
}
这里sum_helper的调用不是尾调用，因为sum_helper返回一个double值，并且sum需要将其转换为int值。
在C ++中，返回可能有各种不同解释的对象引用是很常见的，每种解释都可以是不同的类型转换，例如：
bool write_it(int it) {
return cout << it;
}
这里有一个对cout.operator <<作为最后一个语句的调用。 cout将返回一个对自身的引用（这就是为什么你可以将许多事情串在一起的一个列表，由<<）分隔，然后你强制评估为一个bool，最终调用cout的另一个方法operator bool（ ）。 在这种情况下，这个cout.operator bool（）可以被称为尾部调用，但operator <<不能。
编辑：
值得一提的是，C中tail调用优化的一个主要原因是编译器知道被调用函数将它的返回值存储在相同的地方，因为调用函数必须确保返回值是存储在。
链接地址: http://www.djcxy.com/p/14131.html