constexpr函数评估可以进行尾递归优化

Question

我想知道对于长循环我们是否可以在C++ 11中利用constexpr的尾递归？

Answer 1

根据规则[implimits],允许实现对constexpr计算设置递归深度限制.具有完整constexpr实现的两个编译器(gcc和clang)都使用标准建议的默认512个递归调用来应用这样的限制.对于这两个编译器,以及遵循标准建议的任何其他实现,尾递归优化基本上是不可检测的(除非编译器在达到其递归限制之前否则会崩溃).

实现可以选择仅计算在其递归深度限制中不能应用尾递归优化的调用,或者不提供这样的限制.但是,这样的实现可能会对其用户造成损害,因为它可能会崩溃(由于堆栈溢出)或者无法在constexpr深度或无限递归的评估中终止.

关于达到递归深度限制时会发生什么,Pubby的例子提出了一个有趣的观点.[expr.const]p2指定

调用constexpr函数或constexpr构造函数,它将超出实现定义的递归限制(见附录B);

不是一个恒定的表达.因此,如果在需要常量表达的上下文中达到递归限制,则程序是不正确的.如果constexpr在不需要常量表达式的上下文中调用函数,则通常不需要在转换时尝试对其进行求值,但如果它选择,并且达到递归限制,则需要执行在运行时调用.在完整的,可编译的测试程序中:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
constexpr unsigned long long k = f(0xffffffff);

GCC说:

depthlimit.cpp:4:46:   in constexpr expansion of ‘f(4294967295ull, 0ull)’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
[... over 500 more copies of the previous message cut ...]
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:4:46: error: constexpr evaluation depth exceeds maximum of 512 (use -fconstexpr-depth= to increase the maximum)

和铿说:

depthlimit.cpp:4:30: error: constexpr variable 'k' must be initialized by a constant expression
constexpr unsigned long long k = f(0xffffffff);
                             ^   ~~~~~~~~~~~~~
depthlimit.cpp:2:14: note: constexpr evaluation exceeded maximum depth of 512 calls
  return n ? f(n-1,s+n) : s;
             ^
depthlimit.cpp:2:14: note: in call to 'f(4294966784, 2194728157440)'
depthlimit.cpp:2:14: note: in call to 'f(4294966785, 2190433190655)'
depthlimit.cpp:2:14: note: in call to 'f(4294966786, 2186138223869)'
depthlimit.cpp:2:14: note: in call to 'f(4294966787, 2181843257082)'
depthlimit.cpp:2:14: note: in call to 'f(4294966788, 2177548290294)'
depthlimit.cpp:2:14: note: (skipping 502 calls in backtrace; use -fconstexpr-backtrace-limit=0 to see all)
depthlimit.cpp:2:14: note: in call to 'f(4294967291, 17179869174)'
depthlimit.cpp:2:14: note: in call to 'f(4294967292, 12884901882)'
depthlimit.cpp:2:14: note: in call to 'f(4294967293, 8589934589)'
depthlimit.cpp:2:14: note: in call to 'f(4294967294, 4294967295)'
depthlimit.cpp:4:34: note: in call to 'f(4294967295, 0)'
constexpr unsigned long long k = f(0xffffffff);
                                 ^

如果我们修改代码,以便在翻译时不需要进行评估:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
int main(int, char *[]) {
  return f(0xffffffff);
}

然后两个编译器都接受它,并生成在运行时计算结果的代码.构建时-O0,此代码由于堆栈溢出而失败.构建时-O2,编译器的优化器将代码转换为使用尾递归并且代码正确运行(但请注意,此尾递归与constexpr评估无关).