blocks|key|1269502|text|C%2B%2B中的尾部递归看起来与C或任何其他语言相同。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1269503|void+countdown(+int+count+)+{
++++if+(+count+)+return+countdown(+count+-+1+);
}|code-block|syntax|javascript|1269504|尾递归(和一般的尾部调用)需要在执行尾部调用之前清除调用者的堆栈框架。对于程序员来说，尾递归类似于循环，return简化为像goto+first_line;一样工作。但是，编译器需要检测你在做什么，如果它没有检测到，仍然会有一个额外的堆栈框架。大多数编译器都支持它，但是编写循环或goto通常更容易，风险也更小。|offset|length|style|CODE|1269505|非递归尾调用可以启用随机分支(就像goto到其他函数的第一行)，这是一种更独特的工具。|1269506|请注意，在C%2B%2B中，在return语句的作用域中不能有任何具有非平凡析构函数的对象。函数结束清理将要求被调用者返回到调用者，从而消除尾部调用。|1269507|还要注意(在任何语言中)，尾递归要求算法的整个状态在每一步都通过函数参数列表传递。(这一点很明显，因为要求在下一次调用开始…之前消除函数的堆栈框架您不能将任何数据保存在局部变量中。)此外，在函数返回尾部之前，不能对函数的返回值应用任何操作。|1269508|int+factorial(+int+n,+int+acc+=+1+)+{
++++if+(+n+==+0+)+return+acc;
++++else+return+factorial(+n-1,+acc+*+n+);
}|1269509|entityMap^0|0|0|1G|6|1Q|G|3W|4|0|H|4|0|B|6|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Y|8|@$I|Z|J|10|K|L]|$I|11|J|12|K|L]|$I|13|J|14|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|15|8|@$I|16|J|17|K|L]]|9|@]|A|$]]|$1|O|3|P|5|6|7|18|8|@$I|19|J|1A|K|L]]|9|@]|A|$]]|$1|Q|3|R|5|6|7|1B|8|@]|9|@]|A|$]]|$1|S|3|T|5|D|7|1C|8|@]|9|@]|A|$E|F]]|$1|U|3|-4|5|6|7|1D|8|@]|9|@]|A|$]]]|V|$]]

Tail recusion in C++ looks the same as C or any other language.

<pre><code>void countdown( int count ) {
 if ( count ) return countdown( count - 1 );
}
</code></pre>

Tail recursion (and tail calling in general) requires clearing the caller's stack frame before executing the tail call. To the programmer, tail recursion is similar to a loop, with <code>return</code> reduced to working like <code>goto first_line;</code>. The compiler needs to detect what you are doing, though, and if it doesn't, there will still be an additional stack frame. Most compilers support it, but writing a loop or <code>goto</code> is usually easier and less risky.

Non-recursive tail calls can enable random branching (like <code>goto</code> to the first line of some other function), which is a more unique facility.

Note that in C++, there cannot be any object with a nontrivial destructor in the scope of the <code>return</code> statement. The end-of-function cleanup would require the callee to return back to the caller, eliminating the tail call.

Also note (in any language) that tail recursion requires the entire state of the algorithm to be passed through the function argument list at each step. (This is clear from the requirement that the function's stack frame be eliminated before the next call begins… you can't be saving any data in local variables.) Furthermore, no operation can be applied to the function's return value before it's tail-returned.

<pre><code>int factorial( int n, int acc = 1 ) {
 if ( n == 0 ) return acc;
 else return factorial( n-1, acc * n );
}
</code></pre>

blocks|key|1269545|text|Wikipedia+has+a+decent+article+on+tail+recursion。基本上，尾递归比常规递归更好，因为将其优化为迭代循环很简单，而且迭代循环通常比递归函数调用更有效。这在没有循环的函数式语言中尤其重要。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1269546|对于C%2B%2B，如果您可以使用尾递归编写递归循环，这仍然很好，因为它们可以进行更好的优化，但在这种情况下，您通常可以在一开始就迭代地进行，因此收益不像在函数式语言中那么大。|1269547|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Tail_recursion^0|0|1C|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

<a href="http://en.wikipedia.org/wiki/Tail_recursion" rel="nofollow noreferrer">Wikipedia has a decent article on tail recursion</a>. Basically, tail recursion is better than regular recursion because it's trivial to optimize it into an iterative loop, and iterative loops are generally more efficient than recursive function calls. This is particularly important in functional languages where you don't have loops.

For C++, it's still good if you can write your recursive loops with tail recursion since they can be better optimized, but in such cases, you can generally just do it iteratively in the first place, so the gain is not as great as it would be in a functional language.

Can someone show me a simple tail-recursive function in C++?

Why is tail recursion better, if it even is?

What other kinds of recursion are there besides tail recursion?

Tail recursion in C++

编译器

谁能用C++给我演示一个简单的尾递归函数？为什么尾递归更好，如果它是的话？除了尾递归之外，还有其他类型的递归吗？

问C++中的尾递归
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++中的尾递归EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C++中的尾递归
EN