在C ++中的尾recursion
有人能告诉我一个简单的尾recursion函数在C + +？
为什么尾部recursion更好呢？
还有什么其他types的recursion除了尾recursion吗？
一个简单的尾recursion函数：
unsigned int f( unsigned int a ) { if ( a == 0 ) { return a; } return f( a - 1 ); // tail recursion }
尾recursion基本上是这样的：
- 只有一个recursion调用
- 该调用是函数中的最后一个语句
而且它不是“更好”的，除非一个好的编译器可以移除recursion，转换成一个循环。 这可能会更快，肯定会节省堆栈使用。 GCC编译器可以做这个优化。
C ++中的尾部清除与C或任何其他语言相同。
void countdown( int count ) { if ( count ) return countdown( count - 1 ); }
尾recursion（一般尾调用）需要在执行尾调用之前清除调用者的栈帧。 对于程序员来说，尾recursion类似于一个循环， return就像goto first_line; 。 但编译器需要检测你在做什么，如果没有，还是会有一个额外的堆栈框架。 大多数编译器都支持它，但是编写循环或goto通常更容易，风险更小。
非recursion尾部调用可以使随机分支（如goto其他函数的第一行），这是一个更独特的设施。
请注意，在C ++中，在return语句的范围内不能有任何具有不平凡析构函数的对象。 函数结束清理将要求被调用者返回给调用者，消除尾部调用。
还要注意（用任何语言）尾recursion要求整个algorithm的状态在每一步都要通过函数参数列表。 （从下面的调用开始之前消除函数的堆栈帧的要求是很明显的…你不能将任何数据保存在本地variables中。）另外，在函数的尾部返回之前，不能将操作应用到函数的返回值。
int factorial( int n, int acc = 1 ) { if ( n == 0 ) return acc; else return factorial( n-1, acc * n ); }
尾recursion是尾调用的特例。 尾部调用是编译器可以看到从被调用函数返回时不需要执行任何操作的地方 – 从本质上说，调用函数的返回就是它自己的。 编译器通常可以执行一些堆栈修复操作，然后跳转（而不是调用）到被调用函数的第一条指令的地址 。
关于这一点，除了消除一些回电之外，还有一个好处就是减less了堆栈的使用。 在某些平台或操作系统代码中，堆栈可能非常有限，并且在像我们桌面上的x86 CPU这样的高级计算机上，堆栈使用率会降低，这样可以提高数据高速caching的性能。
尾recursion是被调用函数与调用函数相同的地方。 这可以转化为循环，这与上面提到的尾部调用优化中的跳转完全相同。 由于这是相同的function（被调用者和调用者），因此在跳转之前需要完成的堆栈修改较less。
下面显示了一个通常的方法来做一个recursion调用，这会使编译器变得更加困难：
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完成所有的math运算。
既然你在你的问题中提到了C ++，我会提到一些特别的事情。 C ++隐藏了C没有的东西。 在这些析构函数中，最主要的是会影响尾部调用优化。
int boo(yin * x, yang *y) { dharma z = x->foo() + y->bar(); return z.baz(); }
在这个例子中，对baz的调用并不是一个真正的尾巴调用，因为z需要在从baz返回之后被破坏。 我相信，即使在调用期间不需要variables的情况下，C ++的规则也可能使得优化更加困难，例如：
int boo(yin * x, yang *y) { dharma z = x->foo() + y->bar(); int u = z.baz(); return qwerty(u); }
在qwerty返回之后，z可能不得不被破坏。
另一件事是隐式types转换，它也可以在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 ++中，返回可能有各种不同解释的对象引用是很常见的，每种解释都可以是不同的types转换，例如：
bool write_it(int it) { return cout << it; }
这里有一个叫做cout.operator的作为最后一个陈述。 cout将返回一个对自身的引用（这就是为什么你可以把许多东西串在一起，用<<分开的列表），然后你强制被评估为bool，最后调用另一个cout的方法operator bool ）。 在这种情况下，这个cout.operator bool（）可以被称为尾部调用，但operator <<不能。
编辑：
有一点值得一提的是，C中tail调用优化的一个主要原因是编译器知道被调用的函数将它的返回值存储在相同的地方，因为调用函数必须确保返回值是存储在。
在C ++编译器级，尾recursion并不存在。
尽pipe你可以编写使用尾recursion的程序，但是你不能通过支持编译器/解释器/语言来获得尾recursion的inheritance优势。 例如，Scheme支持一个尾recursion优化，所以它基本上会将recursion更改为迭代。 这使得堆栈溢出变得更快速和无懈可击。 C ++没有这样的事情。 （至less不是我见过的任何编译器）
显然，MSVC ++和GCC都存在尾recursion优化。 看到这个问题的细节。
维基百科有一个体面的文章尾巴recursion 。 基本上，尾recursion优于常规recursion，因为将其优化为迭代循环是微不足道的，迭代循环通常比recursion函数调用更有效。 在没有循环的函数式语言中，这一点尤为重要。
对于C ++来说，如果你可以使用尾recursion来编写你的recursion循环，那么它仍然是一件好事，因为它们可以被更好地优化，但是在这种情况下，你通常可以只是迭代地进行迭代，所以获得的效果并不像它那么好用function语言。
尾recursion是实际上同时处理两个问题的一个技巧。 第一个是在很难知道迭代次数的时候执行一个循环。
虽然这可以用简单的recursion来解决，但第二个问题是由于recursion调用被执行太多而导致堆栈溢出。 尾随呼叫是一种“计算和携带”技术的解决scheme。
在基本的CS中，您将了解到计算机algorithm需要具有不变和终止条件。 这是构build尾recursion的基础。
- 所有的计算都发生在parameter passing中。
- 所有结果都必须传递给函数调用。
- 尾部呼叫是最后一次呼叫，并在终止时发生。
简单的说， 函数的返回值不能计算 。
以10的幂的计算为例，这是微不足道的，可以通过循环来写。
应该看起来像
template<typename T> T pow10(T const p, T const res =1) { return p ? res: pow10(--p,10*res); }
这给了一个执行，例如4：
RET，P，RES
– ， – 4,1
– ，3,10
– 2100
– ，1,1000
– ，0,10000
10000， – ， –
很显然，编译器只需要复制值而不改变堆栈指针，并且只在返回结果时发生尾部调用。
尾recursion是非常重要的，因为它可以提供现成的编译时间评估，例如上面可以做成。
template<int N,int R=1> struct powc10 { int operator()() const { return powc10<N-1, 10*R>()(); } }; template<int R> struct powc10<0,R> { int operator()() const { return R; } };
这可以用作powc10<10>()()来计算编译时的10次幂。
大多数编译器有嵌套调用的限制，所以尾调用技巧有帮助。 显然，没有元编程循环，所以不得不使用recursion。
