¿Cómo funciona la recursión en tiempo de compilación?

Question

me encontré con un código aquí Printing 1 to 1000 without loop or conditionals

Por favor alguien puede explicar cómo funciona el tiempo de compilación de recursividad, no podían encontrar en Google

// compile time recursion 
template<int N> void f1() 
{ 
    f1<N-1>(); 
    cout << N << '\n'; 
} 

template<> void f1<1>() 
{ 
    cout << 1 << '\n'; 
} 


int main() 
{ 
    f1<1000>(); 
} 

Gracias!

Answer 1

Se crea una instancia reiterada de la plantilla f1<N> con valores decrecientes para N (f1<N>() llamadas f1<N-1> y así sucesivamente). La especialización explícita para N==1 finaliza la recursión: tan pronto como N se convierta en 1, el compilador seleccionará la función especializada en lugar de la plantilla.

f1<1000>() hace que el compilador crea una instancia de f1<N> 999 veces (sin contar en la llamada final al f1<1>). Esta es la razón por la que puede llevar un tiempo compilar código que hace un uso intensivo de las técnicas de metaprogramación de plantillas.

Todo depende en gran medida de las habilidades de optimización del compilador; idealmente, debería eliminar la recursión (que solo sirve como hack para emular un bucle for utilizando plantillas) por completo.

Answer 2

Funciona conceptualmente casi de la misma manera que la recursión en tiempo de ejecución. f1<1000> llama al f1<999> y luego imprime 1000. f1<999> llama al f1<998> y luego imprime 999, etc. Una vez que llega a 1, la especialización de plantilla actúa como el caso base para cancelar la recursión.

Answer 3

Bastante simple, cada instanciación de plantilla crea una nueva función con el parámetro modificado. Como si definieras: f1_1000(), f1_999() y así sucesivamente.

Cada función llama a la función con 1 menos en su nombre. Como hay una plantilla diferente, no recursiva, para definir f1_1() también tenemos un caso de detención.

Answer 4

No se garantiza que sea una recursión en tiempo de compilación pura. El compilador tendrá que instanciar la función f1() para todos los parámetros de 2 a 1000 y se llamarán entre sí.

Luego el compilador puede ver que esas llamadas se pueden convertir en una secuencia de declaraciones cout << .... Tal vez elimine las llamadas, tal vez no, esto depende del compilador. Desde el punto de C++, esta es una cadena de llamadas a funciones y el compilador puede hacer lo que sea, siempre que no altere el comportamiento.

Answer 5

Tiene un cálculo factorial explicado here.

por cierto que tenga en cuenta que su función no funciona para números negativos.