Post on 21-Jan-2016
description
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!*/