Шаблонная функция шаблона без специализации шаблона

Я не понимаю следующее поведение.

Следующий код, предназначенный для вычисления факториала во время компиляции, даже не компилируется:

#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

Проблема здесь в том, что ваш оператор 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 С++ 17 способ остановить это - использовать специализацию для 0, которая разрывает эту цепочку. Начиная с С++ 17 с constexpr, если, это больше не требуется. Использование

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, поэтому вы не будете продолжать спускаться по кроличьей норе.

Ответ 2

Проблема в том, что 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>();
}

Имейте в виду, это решение довольно плохое (одно и то же условие терминала должно быть повторено дважды), я пишу этот ответ просто для того, чтобы показать, что всегда есть больше способов решить проблему: -)