Consideriamo di nuovo il problema di inserire un elemento in una lista ordinata, in modo tale che la lista rimanga ordinata. Anche in questo caso, usiamo una funzione ricorsiva, che risulterà essere molto più semplice della funzione iterativa vista in precedenza.
Usiamo ancora la definizione ricorsiva di lista. Se la lista è vuota, allora l'elemento va inserito nella lista, che dopo conterrà quindi solo l'elemento da inserire.
Consideriamo ora il caso di lista non vuota. Sia quindi la lista costituita da un primo elemento x e dal resto della lista. Sono possibili due casi. Se x è maggiore dell'elemento da inserire, allora questa va inserito in testa alla lista. Se l'elemento da inserire è invece maggiore di x, allora l'elemento non va inserito prima di x. Quindi va inserito dopo, ossia va inserito nel resto della lista. Anche qui, facciamo l'ipotesi che la chiamata ricorsiva inserisce correttamente l'elemento nel resto della lista.
In questo caso, è fondamentale il fatto che l'inserimento in lista ordinata funziona anche nel caso in cui l'elemento va inserito in prima posizione. In questo caso, se l'elemento va messo prima di x, allora lo si mette in prima posizione. Nel caso in cui va inserito dopo x, allora va messo o in seconda posizione oppure in una posizione successiva. Questo non fa nessuna differenza, dato che si tratta di inserire l'elemento, eventualmente in prima posizione, nel resto della lista.
La funzione complessiva, contenuta nel programma insordri.c, è la seguente.
void InserimentoListaOrdinata(TipoLista *pl, int e) {
TipoLista s, t;
/* caso di lista vuota */
if(*pl==NULL) {
*pl=malloc(sizeof(struct NodoLista));
(*pl)->val=e;
(*pl)->next=NULL;
return;
}
/* l'elemento va messo in prima posizione */
if((*pl)->val>e) {
s=malloc(sizeof(struct NodoLista));
s->val=e;
s->next=*pl;
*pl=s;
return;
}
/* l'elemento va aggiunto al resto della lista */
InserimentoListaOrdinata(&(*pl)->next, e);
}
Il caso di lista vuota, evidentemente, questa volta non è un errore: al contrario, si deve semplicemente inserire l'elemento come unico elemento della lista. Se la lista contiene degli elementi, si confronta l'elemento da inserire con il primo della lista. Se è minore, allora va inserito in prima posizione (dopo aver fatto questo, si può terminare la esecuzione senza fare altre chiamate ricorsive). Se l'elemento da inserire è invece maggiore del primo della lista, allora va inserito nel resto della lista, eventualmente in prima posizione. Questo viene realizzato (anche nel caso di inserimento in testa nel resto) facendo la chiamata ricorsiva.
Non è difficile verificare che la funzione è corretta anche nel caso in cui l'elemento va inserito in ultima posizione. Suppondendo che la lista sia (3 9 12 90) e che l'elemento da inserire sia 100, quello che succede è che la prima chiamata ricorsiva confronta 100 con 3, e quindi chiama la funzione sul resto della lista e su 100. Il resto della lista è (9 12 90), per cui si confronta 9 con 100. Quindi si fa la chiamata ricorsiva con (12 90), e quindi anche su (90). Dato che 90 è minore di 100, si deve fare una ulteriore chiamata ricorsiva. Ora, la lista passata contiene solo (90), per cui è la lista composta dal numero 90, e il resto della lista è vuoto. L'ulteriore chiamata ricorsiva riceve la lista vuota, per cui l'elemento viene aggiunto come unico elemento. Questo significa che la lista che prima era composta solo da 90 ora è diventata (90 100), dato che il resto della lista (che prima era vuoto) ora contiene 100. È quindi chiaro che anche tutti gli altri resti di lista sono stati alterati in questo modo, per cui 100 è stato aggiunto in coda alla lista originale.