c++ - 在 C++ 中进行尾递归

Question

如果我执行尾调用递归(而不是 for (;;)...break 循环)，我的函数可以写得更简单。但我担心如果编译器无法优化它，我会遇到性能问题，尤其是因为它将由最终用户编译。

1. 有没有办法告诉编译器“确保优化这个尾调用，否则给我一个错误”(例如 Scala 支持这个)

2. 如果编译器无法优化它，性能限制是什么？在不破坏堆栈的情况下，我预计可以运行多少尾调用？

---

更新:

编译器是 gcc 和 MSVC。

通常，我预计会有十几个尾部调用。但极端情况下可能有数千人。平台是典型的低端笔记本电脑(例如 Core i3 或 i5)。

Answer 1

不，没有办法告诉编译器需要尾递归。一些编译器(我不知道)可能支持特定于实现的注释，但这需要用户使用该特定的编译器。其他一些编译器，在某些模式下，故意从不支持尾调用，因为它们可以通过不支持尾调用来提供更好的调试体验。用户可能正在使用这样的编译器。

允许的递归深度高度依赖于程序、函数和实现，并且无法给出合理的数字。给定一个特定的平台，您可能可以确定默认堆栈大小，调查该平台上某个特定编译器的帧大小，然后进行简单的除法以粗略估计您可以拥有多少嵌套调用。

我建议以一种让读者清楚发生了什么的方式重写它，但不依赖于编译器优化尾调用。尽管讨厌，goto 语句对此非常有用。

采用简单的尾递归位计数函数:

int bitcount(unsigned int n, int acc = 0) {
  if (n == 0)
    return acc;

  return bitcount(n >> 1, acc + (n & 1));
}

它可以简单地重写为

int bitcount(unsigned int n, int acc = 0) {
tail_recurse:
  if (n == 0)
    return acc;

  // tail return bitcount(n >> 1, acc + (n & 1));
  acc += n & 1;
  n = n >> 1;
  goto tail_recurse;
}

当然这是一个简单的版本，为了完全避免递归而被简单地重写，甚至可能不应该手动实现，但我在这里使用的特定转换是您可以应用于任何 可以使用尾递归和需要尾递归的函数。评论应确保读者仍然可以轻松地发现正在发生的事情。