没有模板特化的模板阶乘函数

Question

我不理解以下行为。

以下旨在在编译时计算阶乘的代码甚至无法编译：

#include <iostream>
using namespace std;
template<int N>
int f() {
  if (N == 1) return 1; // we exit the recursion at 1 instead of 0
  return N*f<N-1>();
}
int main() {
  cout << f<5>() << endl;
  return 0;
}

并抛出以下错误：

...$ g++ factorial.cpp && ./a.out 
factorial.cpp: In instantiation of ‘int f() [with int N = -894]’:
factorial.cpp:7:18:   recursively required from ‘int f() [with int N = 4]’
factorial.cpp:7:18:   required from ‘int f() [with int N = 5]’
factorial.cpp:15:16:   required from here
factorial.cpp:7:18: fatal error: template instantiation depth exceeds maximum of 900 (use ‘-ftemplate-depth=’ to increase the maximum)
    7 |   return N*f<N-1>();
      |            ~~~~~~^~
compilation terminated.

然而，在为 N == 0 添加专业化后（上面的模板甚至达不到），

template<>
int f<0>() {
  cout << "Hello, I'm the specialization.\n";
  return 1;
}

代码编译并给出正确的输出，即使从未使用过专业化：

...$ g++ factorial.cpp && ./a.out 
120

Answer 1

这里的问题是您的 if 语句是运行时间结构。当你有

int f() {
  if (N == 1) return 1; // we exit the recursion at 1 instead of 0
  return N*f<N-1>();
}

f<N-1> 被实例化，因为它可能被调用。即使 if 条件会阻止它调用 f<0>，编译器仍然必须实例化它，因为它是函数的一部分。这意味着它实例化 f<4>，它实例化 f<3>，它实例化 f<2>，如此循环往复。

Pre C++17 的方法是使用 0 的特化来打断链条。从使用 constexpr if 的 C++17 开始，不再需要它。使用

int f() {
  if constexpr (N == 1) return 1; // we exit the recursion at 1 instead of 0
  else return N*f<N-1>();
}

保证 return N*f<N-1>(); 甚至不会存在于 1 情况下，因此您不会继续陷入实例化的兔子洞。

Answer 2

问题是 f<N>() 总是实例化 f<N-1>() 无论分支是否被采用。除非正确终止，否则会在编译时创建无限递归（即它会尝试实例化 F<0>，然后 f<-1>，然后 f<-2> 等等）。显然，您应该以某种方式终止该递归。

除了 NathanOliver 建议的 constexpr 解决方案和专业化之外，您可以显式终止递归：

template <int N>
inline int f()
{
    if (N <= 1)
        return 1;
    return N * f<(N <= 1) ? N : N - 1>();
}

注意，这个解决方案很差（相同的终止条件必须重复两次），我写这个答案只是为了表明总是有更多的方法来解决这个问题:-)

没有模板特化的模板阶乘函数

Template factorial function without template specialization

c++

recursion

templates

factorial

template-specialization