La ricorsione risulta particolarmente utile sulle liste collegate. Questo è dovuto al fatto che le liste si possono definire in modo ricorsivo, per cui una funzione ricorsiva si può dimostrare facilmente essere corretta, basandosi appunto su questa definizione ricorsiva.
La definizione di lista usata fino a questo momento è: una lista è una sequenza di dati dello stesso tipo (per esempio, interi). Una definizione alternativa è la seguente:
una lista è: la lista vuota, oppure un elemento seguito da un'altra lista.
In altre parole, una sequenza di elementi può essere composta da zero elementi, oppure da un elemento seguito da altri elementi in sequenza. La definizione di tipo che si usa in C riflette esattamente questa definizione: infatti, una variabile di tipo lista l può valere NULL (che rappresenta la lista vuota), oppure può essere un puntatore a una struttura che contiene un dato più un altro puntatore. Si noti che il puntatore che sta nella struttura è di tipo struct NodoLista *, e che TipoLista è in effetti lo stesso tipo. Possiamo quindi dire che la struttura è composta da un elemento e da un puntatore, che rappresenta un'altra lista.
Per essere ancora più chiari, possiamo usare la seguente definizione di tipo: dato che TipoLista è un puntatore a una struttura struct NodoLista, possiamo dire che il campo next della struttura è di tipo TipoLista, e questo è equivalente alla definizione di tipo data in precedenza:
struct NodoLista {
int val;
TipoLista next;
};
typedef struct NodoLista *TipoLista;
Con questa nuova definizione, la ricorsività appare abbastanza evidente: una variabile dichiarata come TipoLista l può valere NULL, e quindi rappresentare la lista vuota, oppure può essere un puntatore a una struttura che contiene un valore e un'altra variabile l->next che rappresenta un'altra lista.
Per essere più precisi, la variabile di tipo lista l->next rappresenta la lista che è composta da tutti gli elementi tranne il primo. Questo discende immediatamente dalla regola che dice quale è la lista rappresentata da una variabile: è la lista che si ottiene guardando la struttura puntata e poi seguendo i puntatori fino a NULL.
Dalla figura risulta abbastanza chiaro che la lista rappresentata da l è (65 22 -90 32). Nello stesso modo, la lista rappresentata da l->next si ottiene seguendo le freccie, per cui il primo valore è 22 seguito da -90 seguito da 32, per cui la lista è (22 -90 32), che è appunto la stessa lista rappresentata da l tranne il primo elemento. Questo fatto si può capire anche passando l->next alla funzione di stampa di una lista: è evidente che verrà stampata tutta la lista, tranne il primo elemento.
Dalla figura risulta anche chiaro che l'unica cosa che realmente distingue le variabili l e l->next è solo il fatto che la seconda è un campo di una struttura. Come si è però già detto, i campi delle strutture si possono considerare come variabili, e quindi usare in qualsiasi contesto in cui si possono usare variabili normali dello stesso tipo. La lista rappresentata da tutti gli elementi di quella originaria tranne il primo si dice resto della lista. Quindi, per esempio, l->next è il resto della lista l.
Le funzioni ricorsive su liste hanno in genere questa caratteristica: sono funzioni che hanno come argomento una lista l, e al loro interno c'è una chiamata ricorsiva a cui si passa l->next. Queste funzioni normalmente operano su l->val (il primo elemento della lista), e poi agiscono sul resto della lista solo attraverso la chiamata ricorsiva, a cui viene passato appunto il resto della lista, che è l->next.
La regola per scrivere una corretta funzione ricorsiva è la seguente: si assume che la chiamata ricorsiva al suo interno funzioni (ossia che la funzione operi già correttamente sul resto della lista), e si scrive una funzione che opera correttamente su tutta la lista (incluso il primo elemento). Occorre poi che ci siano casi in cui la funzione non chiami ricorsivamente se stessa. Questo viene generalmente garantito dal fatto che la funzione deve essere corretta anche nel caso in cui la lista è vuota (per cui non esiste un resto della lista su cui fare la chiamata ricorsiva).
Consideriamo quindi il problema di stampare una lista. Una funzione di questo genere è abbastanza banale da realizzare in modo iterativo. Vediamo qui la versione ricorsiva. Per prima cosa, una lista o è la lista vuota, oppure è composta da un elemento seguito da un'altra lista. Sia void StampaLista(TipoLista l) la intestazione della funzione, per cui l è la lista passata. Se l rappresenta la lista vuota, non si stampa niente; si esce semplicemente dalla funzione senza fare nulla. Nel caso in cui la lista non è vuota, allora è composta da un elemento l->val e dal resto della lista. Il principio è che possiamo assumere che la chiamata ricorsiva sul resto della lista funziona, per cui mettere dentro la funzione la istruzione StampaLista(l->next) stampa effettivamente il resto della lista, ossia tutti gli elementi tranne il primo.
Abbiamo quindi coperto il caso della lista vuota, e sappiamo che mettendo la istruzione StampaLista(l->next) riusciamo a stampare gli elementi della lista a partire dal secondo, fino alla fine. Dato che vogliamo stampare tutti gli elementi della lista (a partire dal primo), possiamo stampare il primo elemento e poi mettere la istruzione StampaLista(l->next). In altre parole, dato che quest'ultima istruzione stampa gli elementi della lista a partire dal secondo, e che printf("%d ", l->val) stampa il primo, per fare la stampa di tutti basta mettere prima la printf che stampa il primo, e poi la chiamata ricorsiva che stampa tutti i successivi. La funzione complessiva è quindi la seguente:
void StampaLista(TipoLista l) {
if(l==NULL)
return;
printf("%d ", l->val);
StampaLista(l->next);
}
La parte fondamentale di una funzione ricorsiva è chiaramente il caso in cui viene fatta un'altra chiamata alla funzione stessa. In questo caso, si assume che la funzione sia corretta quando viene chiamata sul resto della lista. Non va però dimenticato che la funzione, per essere corretta, deve avere un caso base, ossia si deve sempre, prima o poi, arrivare a una situazione in cui non viene fatta la chiamata ricorsiva. Questo caso viene a volte coperto dal caso in cui la lista è vuota, per cui se la funzione va bene su lista vuota e su lista di più elementi, allora è corretta. Ci sono però dei casi in cui occorre trattare il caso di lista composta da un solo elemento in modo particolare. Questo verrà visto in dettaglio più avanti.
Possiamo quindi riassumere il metodo di scrittura di funzioni ricorsive su liste come segue:
Per concludere, notiamo che questo metodo di scrittura delle funzioni ricorsive è analogo al meccanismo di dimostrazione per induzione in matematica. Quello che in matematica è il caso base, per noi è la lista vuota. Nelle dimostrazioni per induzione, si assume che la tesi sia vera per un certo numero n-1, e la si dimostra vera per n. Nel nostro caso, scriviamo la funzione in modo che sia corretta per una lista di lunghezza generica n assumendo che la chiamata ricorsiva funzioni su una lista di lunghezza n-1 (il resto della lista).
Il programma completo che contiene la stampa della lista con funzione ricorsiva è prntric.c
Vediamo ora l'esecuzione della funzione sulla lista di sopra, ossia (65 22 -90 32). Alla prima chiamata della funzione, abbiamo la seguente situazione.
Disegnamo la lista con la notazione grafica delle liste. Per i record di attivazione questa rappresentazione non è adatta, dato che comunque le variabili devono essere organizzate in gruppi (i record di attivazione) che vanno messi l'uno sopra l'altro.
La esecuzione della funzione provoca la stampa del primo elemento della lista, l->val.
Quando si effettua la prima chiamata ricorsiva, StampaLista(l->next), si calcola il valore di l->next. Nel nostro caso, l->next è l'indirizzo della seconda struttura della lista. Quindi, il valore che viene passato alla funzione è l'indirizzo della seconda struttura della lista. Mettiamo quindi un nuovo record di attivazione, e nel parametro formale ci va l'indirizzo della seconda struttura della lista. Questo equivale a mettere una freccia dal nuovo l alla seconda struttura.
Si fa la stampa di l->val. In questo caso, l ha il valore che si trova nel record più in alto, quindi è l'indirizzo della seconda struttura della lista. Quindi l->val è il secondo elemento della lista. Finora abbiamo quindi stampato il primo e il secondo elemento della lista.
Si fa ora la chiamata ricorsiva. Dato che l contiene l'indirizzo della seconda struttura della lista, l->next è l'indirizzo della terza. Quindi, il valore che viene passato nella chiamata ricorsiva è l'indirizzo della terza struttura. Questo valore viene messo nel parametro formale l del nuovo record di attivazione. Quindi, nel nuovo record di attivazione c'è una variabile l che contiene l'indirizzo della terza struttura della lista, e questo equivale a mettere una freccia.
Si stampa di nuovo l->val, che è il terzo elemento della lista, e si fa di nuovo la chiamata ricorsiva. Viene passato l->next, che è l'indirizzo della quarta struttura, e quindi nel nuovo record di attivazione c'è una variabile l che contiene l'indirizzo della quarta struttura, cosa che si rappresenta con la freccia.
Si stampa ancora l->val, che ora è il quarto elemento della lista. Si noti che, a questo punto, abbiamo effettivamente stampato tutti gli elementi della lista, in ordine. La chiamata ricorsiva ora viene fatta con l->next, che contiene NULL. Si passa quindi NULL, che viene messo nella varibile l del nuovo record di attivazione.
Dato che l vale NULL, la funzione termina senza fare altre stampe e chiamate ricorsive. Dato che le chiamate ricorsive sono state fatte sempre alla fine della esecuzione di ogni funzione, tutte le chiamate ricorsive terminano, con conseguente deallocazione di tutti i record di attivazione della funzione StampaLista.
Si noti che sono stati stampati tutti gli elementi della lista, in ordine. Si vede anche facilmente che la funzione è corretta anche nel caso in cui la lista di partenza è vuota (non si stampa niente). Anche altri casi particolari, come la lista composta da un solo elemento, vengono stampati correttamente.