[C] Visita di una lista in ordine inverso

[desterix95]

Buonasera, qualcuno mi potrebbe spiegare questa funzione per la visita inversa di una lista?

Codice:

void visit_r_backward(struct list *ptr) {
   if (ptr != NULL) {
      visit_r_backward(ptr->next_ptr);
      printf("%f\n",ptr->value);
   }
}

Non capisco come possano essere stampati gli elementi al contrario.
Grazie

[insideworld]

è una funzione ricorsiva:
tu chiami la prima funzione che controlla se ha per mano l'ultimo elemento, se è falsa richiama se stessa sull'elemento successivo, questa seconda funzione fa come la prima ma sul secondo elemento, ovvero controlla se l'elemento su cui lavora è l'ultimo. se non è così richiama nuovamente se stessa sull'elemento successivo(il terzo)... arrivato all'ultimo elemento avrò che il puntatore a Next è NULL, quindi alla prossima chiamata non esegui il corpo dell'if (Non Ricorri e non stampi). a questo punto l'istanza attuale termina e restituisce il controllo alla funzione chiamante che continua dal punto in cui si era fermata( la chiamata ricorsiva) faccio la printf stampando l'elemento corrente(l'ultimo) a questo punto l'istanza attuale termina e restituisce il controllo alla funzione chiamante che lavorava sul penultimo elemento e continua dal punto in cui si era fermata( la chiamata ricorsiva) eseguendo l'istruzione successiva, ovvero la printf dell'elemento corrente(il penultimo) poi ritorna alla funzione chiamante che lavorava sul terzultimo elemento e stampa il terzultimo elemento, ritorna,....ecc... fino ad arrivare alla seconda funzione che stampa il secondo elemento, ritorna alla prima che stampa il primo elemento e ritorna alla funzione precedente (penso il MAIN)
cerco di spiegartela nel caso di una lista di 3 elementi (il Next del 3° punterà a NULL)

Codice:

1°elemento
   if (ptr != NULL) {
      visit_r_backward(ptr->next_ptr);            2°elem
                                                               if (ptr != NULL) {
                                                                  visit_r_backward(ptr->next_ptr);            3°elem
                                                                                                                              if (ptr != NULL) {
                                                                                                                                 visit_r_backward(ptr->next_ptr);
                                                                                                                                 printf("%f\n",ptr->value);
                                                                                           (visitr e printf non verranno eseguiti perchè il2°è l'ultimo elem)
                                                                                                                 (il 3°elem è un puntatore a NULL)
                                                                                                                               }
 

                                                                    printf("%f\n",ptr->value);
                                                                 }
      printf("%f\n",ptr->value);
 }


[desterix95]

Grazie per la lunga risposta. Ho capito bene che con le chiamate della funzione stessa dentro l'if in pratica scorro tutta la lista, ma non mi torna il concetto che poi stampa andando all'indietro con ptr->value. Poi, il printf inizia a essere eseguito quando la funzione dentro l'if arriva a ptr->next_ptr==NULL?

[insideworld]

Siccome la printf è dopo la chiamata ricorsiva, viene eseguita dopo la chiamata ricorsiva
ti ho cercato di fare uno schema nel campo codice, ma nella schermata di modifica lo spazio è più largo, ui è più stretto e va a capo dove non dovrebbe.
Se riesci da PC copia tutto e incollalo in blocco note.
cerco di farti uno schema semplificato

Codice:

1°el         |
if(è vero)  |
  ricorri -->|  2°el
                |  if(vero)
                |    ricorri --> | 3°el
                |                   |    if(falso)//il2° è l'ultimo elem quindi 3°
                |                   |                //sarà un puntatore a NULL
                |                   |      //Non ricorro e Non faccio Printf
                |               <--|-  return;
                |  Printf(2°el) |
            <--|- return;
Printf(1°el)|
return;//ritorna al Main


così dovrebbe essere più chiaro.
Immagina un'asse temporale verticale, ovvero la 1° istruzione in alto è eseguita prima, la 2° subito dopo,...
le linee verticali | servono per segnalare il passaggio da un'istanza a un altra della funzione con le frecce --> che indicano le funzioni che spostano il flusso di esecuzione da un'istanza all'altra.
Ora segui questo diagramma con un foglio in mano e ogni volta che trovi una printf scrivi dall'alto del foglio il numero dell'istanza.
Vedrai che partendo dall'alto la prima stampa che farai è quella del 2°elemento e subito dopo quella del primo. se provi ad ampliare lo schema sarà sempre così.
prendi carta e penna e rifatti questo schema con 5 o 6 elementi e riprova a seguire la sequenza di esecuzione e fare le stampe.
Questo è l'unico modo per capire bene la ricorsione: seguire i flusso di esecuzione e vedere in che ordine vengono eseguite le stampe. Poi se al poso delle printf metti un aggiunta ad una lista o ad un vettore non cambia molto, se non gestire gli indici del vettore o i puntatori della lista per fare in modo che abbia lo stesso comportamento di questo codice.
Ultima cosa: se il codice fosse stato:

Codice:

void visit_r_backward(struct list *ptr) {
   if (ptr != NULL) {
      printf("%f\n",ptr->value);
      visit_r_backward(ptr->next_ptr);
   }
}

ovvero scambiando printf e chiamata ricorsiva, avresti stampato gli elementi nell'ordine " giusto".
Prova a farti lo stesso schema di sopra anche per questa funzione ricorsiva
se hai altri dubbi non esitare a chiedere
Ciao

[apatriarca]

Possiamo immaginare alla nostra chiamata ricorsiva per visitare la lista come ad una passeggiata. Ad ogni chiamata ricorsiva corrisponde una sosta nella nostra passeggiata. Ad ogni sosta possiamo fare un qualche tipo di operazione, andare avanti o decidere invece di tornare indietro. Ogni passeggiata sarà quindi caratterizzata da due fasi: quella di andata in cui si va dal punto di partenza alla destinazione, e quella di ritorno in cui si torna al punto di partenza. Quando facciamo operazioni nel percorso di andata, visitiamo le tappe dalla prima all'ultima, mentre se le facciamo nel percorso di ritorno le tappe verrano visitate al contrario, dalla fine all'inizio. Questa è la ragione per cui nel tuo esempio la lista è stampata al contrario.

Nota che per come funzionano le funzioni ricorsive in linguaggi come il C, queste due fasi ci sono sempre. Non è insomma possibile (a meno di usare delle istruzioni particolari) saltare la fase di ritorno. Questa è in effetti una delle ragioni (le altre sono il maggiore uso di memoria, la possibilità di stack overflow e la minore leggibilità del codice nella maggior parte dei casi) per cui algoritmi iterativi sono spesso preferibili. Alcuni linguaggi o compilatori sono in grado di stabilire che ci sono operazioni solo nella fase di andata e rimuovere la fase di ritorno, ma non è il caso dei più comuni compilatori in C. Le funzioni ricorsive in C sono in effetti usate quasi solo nei corsi universitari/scolastici..

[desterix95]

Ok grazie mille!