首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >哪些C++编译器会进行尾递归优化?

哪些C++编译器会进行尾递归优化?
EN

Stack Overflow用户
提问于 2008-08-29 07:35:48
回答 5查看 47.3K关注 0票数 160

在我看来,在C和C++中同时进行尾递归优化会非常好,但在调试过程中,我似乎从来没有看到一个框架堆栈来表示这种优化。这很好,因为堆栈告诉我递归有多深。然而,优化也是很好的。

有没有C++编译器做过这样的优化?为什么?为什么不行?

我该如何告诉编译器这样做呢?

微软-O3

  • /O2或 GCC:-O2或MSVC

如何检查编译器在特定情况下是否已经这样做了?

对于MSVC的

  • ,启用PDB输出以能够跟踪代码,然后检查代码

  • ..?

我仍然建议如何确定某个函数是否被编译器像这样优化(即使我发现Konrad告诉我假设它是可靠的)

始终可以通过进行无限递归并检查它是否会导致无限循环或堆栈溢出来检查编译器是否做到了这一点(我和GCC一起做了这件事,发现-O2就足够了),但我希望能够检查某个我知道无论如何都会终止的函数。我希望有一个简单的方法来检查这一点:)

经过一些测试后,我发现析构函数破坏了进行这种优化的可能性。有时,更改某些变量和临时变量的作用域以确保它们在返回语句开始之前超出作用域是值得的。

如果在尾部调用之后需要运行任何析构函数,则无法进行尾部调用优化。

EN

回答 5

Stack Overflow用户

回答已采纳

发布于 2008-08-29 07:40:32

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

代码语言:javascript
复制
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.
  • For,使用-O3

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

作为一个有趣的历史注释,在Mark Probst的diploma thesis课程中,对C语言的尾部调用优化被添加到了GCC中。本文描述了实现过程中一些有趣的注意事项。这本书值得一读。

票数 139
EN

Stack Overflow用户

发布于 2008-10-21 03:13:21

gcc 4.3.2完全内联了这个函数(糟糕/琐碎的atoi()实现)到main()中。优化级别为-O1。我注意到,如果我尝试使用它(即使将它从static改为extern,尾递归也会很快消失,所以我不会依赖它来保证程序的正确性。

代码语言:javascript
复制
#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;
}
票数 21
EN

Stack Overflow用户

发布于 2016-02-26 18:28:47

除了显而易见的(编译器不会做这种优化,除非你要求),C++中的尾部调用优化也有一个复杂性:析构函数。

假设如下所示:

代码语言:javascript
复制
   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

编译器不能(通常)对此进行尾调用优化,因为它需要在递归调用返回后调用cls的析构函数。

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

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

票数 20
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/34125

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档