- Un ottimo esempio di funzione ricorsiva è quella che cerca un valore
in un albero binario:
typedef struct nodo { struct nodo * sinistro;
int chiave;
struct nodo * destro;
} nodo;
nodo *cerca (nodo *radice, in valore)
{
if (radice == NULL || radice -> chiave == valore)
return radice;
if (radice -> chiave > valore)
return cerca (radice -> sinistro, valore);
else
return cerca (radice -> destro, valore);
}
- Se il valore non esiste nell'albero (
radice == NULL , non ho più albero)
o se ho trovato il valore (radice -> chiave == valore ) ritorno il puntatore
alla radice (che punta al nodo giusto o è null, quindi non trovato)
- Se la chiave della radice è maggiore del valore da cercare, richiamo
di nuovo la funzione cerca dando come nuova radice il puntatore al sottoalbero
sinistro
- Altrimenti richiamo
di nuovo la funzione cerca dando come nuova radice il puntatore al sottoalbero
destro
|