Informatica 4
La ricorsione
Definizione di ricorsione
• Ricorsione è la proprietà di quei programmi che,
all’interno delle istruzioni che li compongono,
richiamano se stessi
• Per essere richiamato, un programma deve avere
un nome
• Usiamo la seguente notazione per dichiarare che
un programma ha nome “fatt”, prende un certo
valore “n” di tipo intero in input, e restituisce un
risultato anch’esso di tipo intero:
nome e tipo
dei parametri
int fatt(int n)
tipo risultato
restituito
nome
programma
in input
Ricorsione: il caso base
• Caso base: ogni programma ricorsivo deve
avere un caso base, ossia un particolare valore
dell’input per cui la soluzione del problema è
immediata e non c’è bisogno che il
programma richiami se stesso
• Il caso base è necessario perché altrimenti un
programma ricorsivo richiamerebbe se stesso
in ogni caso, e non terminerebbe mai
Il caso base: esempio
• Ad esempio, nel calcolo del fattoriale di un
intero (n! = n x (n-1) x (n-2) x … x 3 x 2 x 1), il
caso base si ha quando n = 0, perché 0! = 1
per definizione
• Nel programma:
if (n==0)
return 1;
Ricorsione: ipotesi ricorsiva
• Prima di affrontare il caso generale, bisogna
supporre di avere risolto un caso leggermente
più semplice
• Questa supposizione costituisce l’ipotesi
ricorsiva
• Nel caso del fattoriale, nel calcolare n!,
supponiamo di conoscere già (n-1)!
• Da notare che il caso leggermente più
semplice è anche più vicino al caso base
Ricorsione: passo
• Il passo è l’istruzione con cui si calcola il risultato
generale a partire dal risultato parziale dato dall’ipotesi
ricorsiva
• Nel caso del fattoriale, n! = n x (n-1)! (da notare che,
omettendo il primo fattore, il resto della definizione di
n! coincide con (n-1)! )
• Nel programma, è in questo caso che c’è il richiamo al
programma stesso, con un parametro diverso, non più
il caso generale con n, ma il caso più semplice on (n-1):
return n*fatt(n-1)
Il significato della ricorsione
• Se siamo nel caso base, bene: risultato
immediato
• Se non siamo nel caso base, siamo in un caso
generale: impostiamo il calcolo, il cui risultato
dipende dal caso un po’ più semplice
• Il caso un po’ più semplice richiama lo stesso
programma che si porrà di nuovo il quesito:
siamo nel caso base?
• E così via fino a quando il caso base è
effettivamente raggiunto e tutti i risultati parziali
e, infine, anche quello generale, si possono
calcolare
Fattoriale ricorsivo
int fatt(int n){
if (n==0)
return 1;
return n*fatt(n-1);
}
/*un else dopo il primo return sarebbe
superfluo perché return comunque conclude
l’esecuzione*/
Esempio di esecuzione
• fatt(3)
– non siamo nel caso base, quindi fatt(3) = 3*fatt(2)
• fatt(2)
– non siamo nel caso base, quindi fatt(2) = 2*fatt(1)
• fatt(1)
– non siamo nel caso base, quindi fatt(1) = 1*fatt(0)
• fatt(0)
– siamo nel caso base: return 1
• una volta che è restituito il risultato 1, si riescono a
calcolare tutti i risultati parziali, fino ad ottenere
fatt(3) = 3*2*1*1 = 6
Parametri formali e attuali
• Quando si scrive il codice di fatt, abbiamo
chiamato “n” il parametro di input, ma esso non
ha un vero valore: lo usiamo solo per scrivere il
codice
• “n” nel codice si chiama “parametro formale”
• Quando usiamo di fatto il codice di fatt per
eseguire un calcolo, scriviamo fatt(3)
• “3” nella chiamata a fatt si chiama “parametro
attuale” (da una traduzione errata da actual che
in inglese vuol dire reale, effettivo)
Ricorsione vs iterazione
• Non è obbligatorio risolvere i problemi
scrivendo programmi ricorsivi
• E’ sempre possibile trovare una soluzione
iterativa, ossia che consista in una ripetizione
di un certo numero di istruzioni, finché la
soluzione non viene trovata
• Tipicamente l’iterazione è realizzata con un
ciclo for
Fattoriale iterativo
int fatt(int n){
int i;
int risultato = 1;
for(i=1;i<=n; i++)
risultato = risultato * i;
return risultato
}
/*alla fine del ciclo for risultato contiene
1*1*2*3*…*(n-1)*n, ossia n!*/