c++ - Función factorial de plantilla sin especialización de plantilla

templates recursion

Question

No entiendo el siguiente comportamiento.

El siguiente código, destinado a calcular el factorial en tiempo de compilación, ni siquiera compila:

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

y arroja el siguiente error:

...$ 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.

mientras que, al agregar la especialización para N == 0 (que la plantilla anterior ni siquiera alcanza),

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

el código se compila y proporciona la salida correcta de, incluso si la especialización nunca se usa:

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

Answer 1

El problema aquí es que su declaración if es una construcción en tiempo de ejecución. Cuando tengas

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

la instancia de f<N-1> se puede denominar. Aunque la condición if evitará que llame a f<0> , el compilador todavía tiene que crear una instancia ya que es parte de la función. Eso significa que crea una instancia de f<4> , que crea una instancia de f<3> , que crea una instancia de f<2> , y así sucesivamente continuará para siempre.

La forma Pre C ++ 17 de detener esto es usar una especialización para 0 que rompa esa cadena. Comenzando en C ++ 17 con constexpr si , esto ya no es necesario. Utilizando

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

garantiza que return N*f<N-1>(); ni siquiera existirá en el caso 1 , así que no sigas bajando por la madriguera del conejo.

Answer 2

El problema es que f<N>() siempre crea una instancia de f<N-1>() ya sea que se tome una rama o no. A menos que se termine correctamente, eso crearía una recursión infinita en tiempo de compilación (es decir, intentaría crear una instancia de F<0> , luego f<-1> , luego f<-2> y así sucesivamente). Obviamente, debe terminar esa recursión de alguna manera.

Además de la solución y especialización constexpr sugerida por NathanOliver, puede terminar la recursión explícitamente:

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

Tenga en cuenta que esta solución es bastante pobre (la misma condición terminal debe repetirse dos veces), estoy escribiendo esta respuesta simplemente para mostrar que siempre hay más formas de resolver el problema: -)