代码之家 › 专栏 › 技术社区 › Enlico

不带模板特化的模板阶乘函数

factorial template-specialization recursion templates c++

Enlico · 技术社区 · 5 年前

我不理解以下行为。

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

#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

1 回复 | 直到 5 年前

NathanOliver 5 年前

这里的问题是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> f<0> f<4> ,它实例化 f<3> ,它实例化 f<2> 一直到永远。

C++的17种停止方法是使用专门化的 0 打破了那条链条。从C++ 17开始 constexpr if ,这不再需要。使用

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 案例,所以你不需要一直去实例化兔子洞。

Igor G 5 年前

问题是 f<N>() 实例化 f<N-1>() 不管是否采取分支。除非正确终止,否则将在编译时创建无限递归(即,它将尝试实例化 F<0> ,那么 f<-1> ,那么 f<-2> 等等)。显然你应该以某种方式终止递归。

除了 constexpr NathanOliver建议的解决方案和专门化,您可以显式终止递归:

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

请注意,这个解决方案是相当糟糕的(相同的终端条件必须重复两次),我写这个答案仅仅是为了说明解决这个问题总是有更多的方法:-)

推荐文章

Abhishek Ojha · 为什么我的代码接受其他数据类型以及模板中的给定数据类型?[副本]

2 年前

TCD · 标准库非类型模板类是否显式实例化?

2 年前

onehundredquestions guy · 在不实例化的情况下将模板函数作为参数传递?[副本]

2 年前

sovesti · 参数较少的模板函数中的演绎

2 年前

KiraHoneybee · 具有构造函数参数的模板化类

2 年前

Seymore Glass · 模板不工作的默认参数

2 年前

Alex Hodges · 是否有一种更惯用的方法来专门化通过模板传递的标志的行为?

2 年前

Alexander Daum · 模板参数中对模板类型的引用

6 年前

ledonter · 为什么注入的类名有时不被视为类模板中的模板名?

6 年前

RBaum · 从WooCommerce“订单保留”和“新订单”电子邮件中删除订单

6 年前