Esta función recursiva me desconcierta, ¿qué está pasando?

Question

Estaba jugando con recursividad e hice esta simple función. Asumí que imprimiría 9-0 a stdout, pero imprime 0-9. No puedo ver cómo sucede eso en absoluto.

int main() 
{ 
     rec(10); 
     return 0; 
} 

int rec(int n){ 
     if(n > 0) 
       printf("%d\n", rec(n -1)); 
     return n; 
} 

Answer 1

Como dice Michael Burr en los comentarios, si usted quiere ver lo que está pasando, compilar con símbolos de depuración habilitada, así:

gcc -o test -g test.c 

Luego ejecuta con gdb como tal.

gdb test 

Entonces, para empezar las cosas en marcha, el tipo

start 

que se rompe en la primera llamada de la función principal. Escriba

step 

para llegar a la línea siguiente en el código, y de ahí en adelante, simplemente pulse ENTER para guardar el repetir el último comando. Si está contento, escriba continue para dejar de avanzar. Verá los valores y las líneas evaluadas en cada etapa que confirmarán las respuestas anteriores.

Espero que proporcione información útil.

Answer 2

La función rec en la línea de printf se evalúa antes de la printf sí mismo. Por lo tanto, la instancia más profunda de la función rec se imprime primero.

Answer 3

Piénsalo así.

rec(10) 
rec(9) 
rec(8) 
rec(7) 
rec(6) 
rec(5) 
rec(4) 
rec(3) 
rec(2) 
rec(1) 
rec(0) 

inicio desenrollar

printf("%d\n", 0); 
printf("%d\n", 1); 
printf("%d\n", 2); 
printf("%d\n", 3); 
printf("%d\n", 4); 
printf("%d\n", 5); 
printf("%d\n", 6); 
printf("%d\n", 7); 
printf("%d\n", 8); 
printf("%d\n", 9); 

Answer 4

Vamos a reescribir el código de la siguiente manera:

int rec(int n){ 
     if(n > 0) 
     { 
       int retval = rec(n -1); 
       printf("%d\n", retval); 
     } 
     return n; 
} 

¿Sería claro por qué 0 impreso por primera vez antes de las 9?

Answer 5

Dado que está creando 9 ambients 9 > 8 > 7 > 6 > 5 > 4> 3 > 2 > 1 > 0, ahora estos ambientes se tratan igual que a(b(c(d(e(f(g())))))), yendo del más profundo al primero.

Recuerda que cuando haces esto printf("%d",n(m)); en realidad no estás imprimiendo nada, estás diciendo "imprime el resultado de n (m)" y luego cuando intenta resolver n (m) estás llamando a otra impresión y diciendo una vez más "resolver n (m-1)".

Ahora, cuando llegue a n (0) devolverá 0 para ser impreso por la última llamada de printf, por lo tanto, a continuación, imprime 0 1 .. 9.

Answer 6

int main() 
{ 
     rec(10); 
     return 0; 
} 

int rec(int n){ 
     if(n > 0) 
       printf("%d\n", rec(n -1)); 
     return n; 
} 

En general, consideran que alguna pieza de código. Decimos que existe una relación directa entre soluciones iterativas y recursivas, de manera que cualquier solución se puede escribir de forma iterativa y viceversa. Sin embargo, en algunos casos se ve que es más fácil expresar un algoritmo recursivamente (por ejemplo, la Torre de Hanoi.) En el caso del código anterior, el equivalente sería el constructo de bucle for.

Esto se puede implementar como una función de la siguiente manera:

void _for(int i, int n) 
{ 
    if(i >= n) return; // TERMINAL<br /> 
    // some expression (ie. printf("%d\n",i);)<br /> 
    _for(i+1,n) // RECURSION<br /> 
} 

Nota: esto se puede extender el uso de punteros de función.