c++ - recursivos - ¿Cómo funciona el tiempo de compilación recursiva?

recursividad informatica

Question

Encontré un código aquí Imprimiendo 1 a 1000 sin bucle o condicionales

¿Alguien puede explicar cómo funciona la recursión del tiempo de compilación, no lo pudo 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

Bastante simple, cada instanciación de plantilla crea una nueva función con el parámetro modificado. Como si hubiera definido: 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 2

Crea una instancia repetida 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 termina la recursión: tan pronto como N convierte en 1, el compilador elegirá la función especializada en lugar de la plantilla.

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

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

Answer 3

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

Answer 4

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

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

Answer 5

Usted tiene el cálculo factorial explicado here .

por cierto, una nota de que su función no funciona para números negativos.