在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;
}

当然这是一个简单的版本,通过简单的重写来完全避免递归,甚至可能不应该手动实现,但是我在这里使用的特定转换是可以应用于任何可以进行尾递归的函数的转换.你需要尾递归的地方.评论应该确保读者仍然可以轻松发现正在发生的事情.