Risolviamo il problema della cancellazione dell'ultimo elemento di una lista usando la ricorsione. Come si vedrà, la funzione che si ottiene è molto più semplice di quella iterativa.
Consideriamo per prima cosa la definizione ricorsiva di lista. Una lista può essere o vuota oppure composta da un elemento e dal resto della lista. Nel caso di lista vuota, si può considerare la cancellazione dell'ultimo elemento come un errore, per cui si stampa un messaggio di errore e si termina il programma. Potremmo anche assumere che cancellare l'ultimo elemento da una lista vuota non abbia effetti: questo dipende da come il problema viene interpretato.
Vediamo ora il passo ricorsivo. Per prima cosa, scriviamo la intestazione della funzione. La lista va passata per indirizzo, dato che, nel caso di lista di un solo elemento, il puntatore iniziale va alterato. Quindi, abbiamo la seguente intestazione: void EliminaUltimoRicorsiva(TipoLista *pl). La ipotesi ricorsiva, in questo caso, è che la funzione realizza la cancellazione dell'ultimo elemento, quando viene passato il resto della lista. In altre parole, si assume che la chiamata ricorsiva sul resto della lista EliminaUltimoRicorsiva(& (*pl)->next ) effettivamente cancelli l'ultimo elemento dal resto della lista. Dalla rappresentazione grafica si capisce che eliminare l'ultimo elemento dal resto della lista, effettivamente lo elimina anche dalla lista complessiva. Supponiamo quindi che la lista passata sia la seguente:
Disegnamo chiaramente la lista complessiva e il resto della lista.
L'ipotesi ricorsiva dice che la chiamata di funzione, passando il resto della lista, elimina l'ultimo elemento dal resto della lista, ossia si arriva alla seguente situazione.
Per definizione, il resto della lista, dopo la cancellazione dell'ultimo elemento, non è più collegata all'ultima struttura, che è stata deallocata. Come si vede chiaramente dalla figura, anche la lista complessiva non contiene più l'ultimo elemento. La funzione ha quindi realizzato la eliminazione dell'ultimo elemento dalla lista.
Occorre ora verificare l'esistenza di un caso base, ossia di un caso in cui non viene effettuata la chiamata ricorsiva. Nel nostro caso, partendo da una lista generica, si fa sempre la chiamata ricorsiva sulla lista che è il resto. Questo termina quando si arriva all'ultima struttura, il cui resto è NULL, ossia la lista vuota. A questo punto, si genera un errore. È quindi chiaro che il passo base non funziona. Anche usando la politica per la quale la cancellazione dalla lista vuota è la lista vuota, quello che si ottiene è che l'ultimo elemento non viene mai cancellato.
In questo caso, la lista vuota genera un situazione particolare, e non può quindi essere il vero passo base della ricorsione. Se consideriamo i casi particolari, ci rendiamo conto che il problema è la lista fatta di un solo elemento. In questo caso, la lista che si ottiene cancellando l'ultimo elemento non si ottiene cancellando l'ultimo elemento dal resto. La lista fatta di un solo elemento è costituita dall'elemento stesso, e il resto della lista è la lista vuota. Il risultato della cancellazione, in questo caso, non è la lista ottenuta cancellando l'ultimo elemento dal resto. È invece la lista vuota. Quindi, l'errore sta nel fatto che la chiamata ricorsiva non va fatta, se la lista contiene un solo elemento. Al contrario, in questo caso si deve deallocare l'unico elemento della lista, che deve diventare la lista vuota.
La funzione finale è la seguente. Nel caso in cui la lista è vuota, si può generare un messaggio di errore e terminare. Se la lista ha un solo elemento, allora questo viene cancellato. In tutti gli altri casi (lista fatta di almeno due elementi), si cancella l'ultimo elemento dal resto della lista. Dato che la funzione prende una lista per indirizzo, e il resto della lista è (*pl)->next, la funzione va chiamata passando & (*pl)->next.
void EliminaUltimoRicorsiva(TipoLista *pl) {
/* lista vuota */
if( *pl==NULL ) {
printf("Tentativo di eliminazione da lista vuota\n");
exit(1);
}
/* lista con un solo elemento */
if( (*pl)->next==NULL ) {
free(*pl);
*pl=NULL;
return;
}
/* lista con piu' elementi */
EliminaUltimoRicorsiva( & (*pl)->next );
}
Il programma complessivo che contiene questa funzione è delultri.c