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:int fatt(int n)

tipo risultato restituito

tipo risultato restituito

nome programma

nome programma

nome e tipo dei parametri

in input

nome e tipo dei parametri

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 ottenerefatt(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!*/