Questa funzione ricorsiva mi infastidisce, cosa sta succedendo?

Question

Stavo giocando con la ricorsione e ho fatto questa semplice funzione. Supponevo che avrebbe stampato 9-0 per lo stdout, ma stampa 0-9. Non riesco a vedere come ciò avvenga.

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

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

Answer 1

Come Michael Burr dice nei commenti, se volete vedere cosa sta succedendo, compilare con i simboli di debug attivata, in questo modo:

gcc -o test -g test.c 

Quindi esegui con gdb in questo modo.

gdb test 

Quindi, per iniziare cose in corso, tipo

start 

che si rompe alla prima chiamata nella funzione principale. Type

step 

per arrivare alla riga successiva nel codice, e da allora in poi, basta premere Invio per continuare a ripetere l'ultimo comando. Se sei felice, digita continue per interrompere il passaggio. Vedrai i valori e le linee valutate in ogni fase che confermeranno le risposte di cui sopra.

Spero che fornisca alcune informazioni utili.

Answer 2

La funzione rec sulla linea printf viene valutata prima della printf stessa. Pertanto l'istanza più10 della funzione rec viene stampata prima.

Answer 3

Pensa a questo.

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

Inizio svolgimento

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

Riscriviamo il codice in questo modo:

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

La rende chiaro perché 0 stampato prima di 9?

Answer 5

Perché stai creando 9 ambienti 9 > 8 > 7 > 6 > 5 > 4> 3 > 2 > 1 > 0, ora questi ambienti sono trattati allo stesso modo questo sarebbe a(b(c(d(e(f(g())))))), passando dal più profondo al primo.

Ricordare che quando si esegue questa operazione printf("%d",n(m)); in realtà non si stampa nulla, si sta dicendo "stampa il risultato di n (m)", quindi quando si tenta di risolvere n (m) si chiama un'altra stampa e dicendo ancora una volta "risolvere n (m-1)".

Ora, quando si raggiunge n (0) tornerà 0 per essere stampato da l'ultima chiamata di printf, quindi viene stampato 0 allora 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; 
} 

In generale, si consideri qualche pezzo di codice. Diciamo che esiste una relazione diretta tra soluzioni iterative e ricorsive in modo tale che qualsiasi soluzione possa essere scritta in modo iterativo e viceversa. Tuttavia, in alcuni casi è più facile esprimere un algoritmo in modo ricorsivo (ad esempio Torre di Hanoi.) Nel caso del codice sopra l'equivalente sarebbe il costrutto for loop.

Ciò può essere implementato come una funzione come segue:

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, questo può essere estesa utilizzando puntatori a funzione.