哪些C++编译器(如果有的话)进行尾部递归优化?

当前所有主流编译器都执行尾部调用优化 相当不错(并且已经做了十多年), even for mutually recursive calls 例如:

int bar(int, int);

int foo(int n, int acc) {
    return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
    return (n == 0) ? acc : foo(n - 1, acc + 1);
}

让编译器进行优化很简单:只需打开速度优化:

• 对于MSVC,使用 /O2 或 /Ox .
• 对于GCC、Clang和ICC,请使用 -O3

检查编译器是否进行了优化的一个简单方法是执行一个调用,否则会导致堆栈溢出或查看程序集输出。

作为一个有趣的历史记录,在GCC中添加了C的尾部调用优化 diploma thesis 马克·普罗布斯特。本文描述了实现过程中一些有趣的注意事项。值得一读。

除了显而易见的(除非你要求,否则编译器不会进行这种优化)之外,C++中的尾部调用优化也很复杂:析构函数。

给出如下内容:

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

编译器(通常)不能通过尾部调用来优化它,因为它需要 调用析构函数 cls 之后 递归调用返回。

有时编译器可以看到析构函数没有外部可见的副作用(因此可以提前完成),但通常不能。

一种特别常见的形式是 Funky 实际上是一个 std::vector 或类似。

gcc 4.3.2完全内联了这个函数(蹩脚/琐碎 atoi() 实施) main() 。优化级别为 -O1 。我注意到如果我玩它(甚至把它从 static 向 extern ,尾部递归很快就会消失,所以我不会依赖它来保证程序的正确性。

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}

大多数编译器在调试构建中不会进行任何优化。

如果使用VC,请尝试打开PDB信息的发布版本-这将让您跟踪优化的应用程序,您应该希望看到您想要的内容。然而,请注意,调试和跟踪优化的构建会让你四处奔波,而且通常你不能直接检查变量,因为它们只会出现在寄存器中或完全优化。这是一次“有趣”的经历。..

正如Greg提到的,编译器不会在调试模式下执行此操作。调试构建比prod构建慢是可以的,但它们不应该更频繁地崩溃:如果你依赖于尾部调用优化,它们可能会这样做。因此,最好将尾部调用重写为正常循环。 :-(