在gcc / g ++中的尾递归 [英] Tail recursion in gcc/g++

问题描述

我尝试过搜索，但无法找到：函数的必备条件是什么，以便gcc优化尾递归？有没有包含最重要案例的参考或列表？由于这是特定版本，我的兴趣是4.6.3或更高版本（越新越好）。但是，事实上，任何具体的参考将不胜感激。

预先感谢！

解决方案

启用 -O2 后，如果可能，gcc将执行尾部调用优化。现在，问题是：什么时候有可能？

每当递归调用发生在紧邻的前面时，可以消除单个递归调用或者在（单个） return 语句中，所以除了可能返回不同的值之外，没有可观察的副作用。这包括返回涉及三元运算符的表达式。

请注意，即使在返回表达式中存在几个递归调用（例如在众所周知的斐波那契示例中： return（n == 1）？1：fib（n-1）+ fib（n-2）; ），尾调用递归仍然适用，但只有最后一次递归调用。

作为一个明显的特例，如果编译器可以证明递归函数（及其参数）符合常量表达式，则它可以（最高可配置的最大值递归深度，默认为500）不仅消除尾部调用，而且消除函数的全部执行。这是GCC经常在 -O2 中可靠地执行的事情，它甚至包括对某些库函数的调用，如 strlen 在文字上。

I've tried to search, but was unable to find: what are requisites for functions so that gcc would optimize the tail recursion? Is there any reference or list that would contain the most important cases? Since this is version specific, of my interests are 4.6.3 or higher versions (the newer the better). However, in fact, any concrete reference would be greatly appreciated.

Thanks in advance!

解决方案

With -O2 enabled, gcc will perform tail call optimization, if possible. Now, the question is: When is it possible?

It is possible to eliminate a single recursive call whenever the recursive call happens either immediately before or inside the (single) return statement, so there are no observable side effects afterwards other than possibly returning a different value. This includes returning expressions involving the ternary operator.
Note that even if there are several recursive calls in the return expression (such as in the well-known fibonacci example: return (n==1) ? 1 : fib(n-1)+fib(n-2);), tail call recursion is still applied, but only ever to the last recursive call.

As an obvious special case, if the compiler can prove that the recursive function (and its arguments) qualifies as constant expression, it can (up to a configurable maximum recursion depth, by default 500) eliminate not only the tail call, but the entire execution of the function. This is something GCC does routinely and quite reliably at -O2, which even includes calls to certain library functions such as strlen on literals.

这篇关于在gcc / g ++中的尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！