c++ - G++尾递归优化失败

Question

我将此问题基于对我问here的上一个问题的评论。用户回答我可以具有无限的尾递归堆栈。但是，这不是我在实践中发现的。为了说明我的观点，请看一下我的代码:

#include <iostream>
#include <string>

void tail_print(string& in, size_t& index) //prints in backwards
{
  if (index == 0)
    {
      cout << '$' << endl;
      return;
    }

  cout << in[index];
  index--;
  tail_print(in, index);
}

int main()
{
  string a("abc$");
  size_t pos = a.length()-1;
  tail_print(a, pos);
  return 0;
}

假设输入字符串 in包含以下范围内的字符:1 该代码使用以下命令编译: g++ -pipe -std=c++14 -O2 $file -lm -o exe这将引发信号11(SIGSEG)。我无法精确判断出哪个输入失败，但是我可以肯定地说出该信号的原因是在此子例程中(如果我使用for循环向后打印字符，则可以正常工作)。请注意，这是较大程序的一部分，因此可能会出现不可预见的并发症(可能性很小)。无论采用哪种方式，如果尾部递归优化引起了可观的O(百万)深度的堆栈溢出，我都必须对它进行质疑。
我正在使用以下g++版本:

~$ g++ --version
g++ (Ubuntu 5.5.0-12ubuntu1~16.04) 5.5.0 20171010

Answer 1

如果您依赖尾部递归，那么编译器是否选择优化代码就任其摆布。调试版本不会得到优化，因此将始终失败。
就您而言，通过std::cout打印单个字符似乎是造成此问题的原因。 libstdc++似乎通过调用以下命令实现了打印单个字符:

std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)

由于某种原因，这似乎使GCC 10之前的尾部递归优化失败了。所有Clang版本也未能对此进行优化。
用 cout << in[index]替换 std::cout.put(in[index])似乎允许所有版本的GCC(至少降至4.1.2)和Clang优化尾部递归: https://godbolt.org/z/Th1bT8
有趣的是，直接调用 std::__ostream_insert也是可以的(但不要那样做，因为那样您将依赖于内部libstdc++实现细节): https://godbolt.org/z/9M5xd4
我认为通过 libstdc++中的各个级别的函数调用，您最终都会(由于值取用了 char函数参数):

char c = in[index];
std::__ostream_insert<char, std::char_traits<char> >(std::cout, &c, 1);

创建指向局部变量的指针似乎可以防止尾部递归: https://godbolt.org/z/KM4jGY，大概是因为编译器无法知道被调用函数将对该指针执行的操作，因此无法保证使用循环将具有相同的行为。
由于所有尾部递归都可以用循环轻松替换，因此最好不要依赖于编译器的变数来为您完成操作，因此即使在未优化的构建中也可以使用:

void tail_print(const std::string& in, size_t index) //prints in backwards
{
    for (size_t i = index; i > 0; i--)
    {
        std::cout << in[i];
    }
    std::cout << "$\n";
}