DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
La RicorsioneLa Ricorsione
Marco D. Santambrogio – [email protected]. aggiornata al 29 Maggio 2014
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
ObiettiviObiettivi
• La ricorsione
Ricordate la sigla GNUGNU = GNU is Not Unix
GNU = GNU is Not Unix GNU = GNU is Not Unix
GNU = GNU is Not GNU = GNU
2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
La ricorsione: definizioneLa ricorsione: definizione
• Dal latino re-currere ricorrere, fare ripetutamente la stessa
azione• In informatica: si tratta di
procedure/funzioni che richiamano se stesse
• Il concetto di ricorsione viene usato nel contesto di: algoritmi strutture dati
3
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
La ricorsione: che cos’è?La ricorsione: che cos’è?
• Ricorsione indiretta: Un sottoprogramma P chiama un
sottoprogramma Q Q a sua volta chiama un terzo R, … R chiama nuovamente P
• Ricorsione diretta Un sottoprogramma P chiama se
stesso durante la propria esecuzione
4
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Un esempio classicoUn esempio classico
• Individuare, in un gruppo di palline l’unica pallina di peso maggiore delle altre facendo uso di una bilancia “a basculla”
• Per semplicità: il numero di palline sia una potenza di 3
• Algoritmo Pesate:• Se il gruppo di palline consiste in una sola pallina,
allora essa è banalmente la pallina cercata, altrimenti procedi come segue.
– Dividi il gruppo di palline in tre e confronta due dei tre sottogruppi.
– Se i due gruppi risultano di peso uguale scarta entrambi, altrimenti scarta il gruppo non pesato e quello risultato di peso minore.
– Applica l’algoritmo Pesate al gruppo rimanente.
5
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Altri esempi di ricorsioneAltri esempi di ricorsione
• La sommatoria di una sequenza di numeri
• Fattoriale:
• In arte e non solo…
6
Fact(n)=n*Fact(n-1)Fact(0)=1
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Scopo della programmazione Scopo della programmazione ricorsivaricorsiva
• Lo scopo è quelo di risolvere un problema facendo riferimento allo stesso problma su scala ridotta
• La condizione di terminazione avviene quando si identifica uno o più casi semplici con soluzione immediata
• La struttura di un algoritmo ricorsivo è il seguente
if (è il caso semplice)risolvilo
elseusa la ricorsione su dati ridotti
7
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il calcolo del fattorialeIl calcolo del fattoriale
In matematica, se n è un intero positivo, si definisce n fattoriale e si indica con n! il prodotto dei primi n numeri interi positivi minori o uguali di quel numero
8
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il main del fattorialeIl main del fattoriale
9
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il fattoriale iterativoIl fattoriale iterativo
10
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Definizione ricorsiva del fattorialeDefinizione ricorsiva del fattoriale
1) n!=1 se n=02) n!= n*(n-1)! se n>0
Riduce il calcolo a un calcolo più semplice
Ha senso perché si basa sempre sul fattoriale del numero più piccolo, che io conosco
Ha senso perché si arriva a un punto in cui non è più necessario riusare la def. 2) e invece si usa la 1)
1) è il passo base, 2) è il passo di ricorsione
11
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Esempio di tracciaEsempio di traccia
• Calcoliamo il fattoriale di 4:• 4=0? No: calcoliamo il fattoriale di 3 e molt. per 4• 3=0? No: calcoliamo il fattoriale di 2 e molt. per 3• 2=0? No: calcoliamo il fattoriale di 1 e molt. per 2• 1=0? No: calcoliamo il fattoriale di 0 e molt. per 1• 0=0? Si: il fattoriale di 0 è 1. Risaliamo:• il fattoriale di 1 è 1 per il fattoriale di 0 cioè 1*1=1• il fattoriale di 2 è 2 per il fattoriale di 1 cioè 2*1=2• il fattoriale di 3 è 3 per il fattoriale di 2 cioè 3*2=6• il fattoriale di 4 è 4 per il fattoriale di 3 cioè
4*6=24
12
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
n = 3 main
fat= FattRic(3)
fat= FattRic(2)
fat= FattRic(1)
fat= FattRic(0)
Il fattoriale ricorsivoIl fattoriale ricorsivo
Calcolo del Fattoriale in modo ricorsivo:
1
1
2
6
Fact(n)=n*Fact(n-1)Fact(0)=1
13
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
MoltiplicazioneMoltiplicazione
• Ideare un procedimento ricorsivo per calcolare il prodotto di due interi
• Nota: A*1=A; A*B = A + A*(B-1)
int MulRic(int a, int b){int ris;if (b == 1) ris = a;else ris = a + MulRic(a ,b–1);return ris;
}
14
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
FibonacciFibonacci
• Leonardo Fibonacci Matematico italiano Compie numerosi viaggi e
assimila le conoscenze matematiche del mondo arabo,
Nel 1202 pubblica: il Liber abaci
Con Liber abaci si propose di diffondere nel mondo scientifico occidentale le regole di calcolo note agli Arabi• il sistema decimale
15
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Il problema dei “Il problema dei “conigliconigli””
“Un tale mise una coppia di conigli in un luogo completamente circondato da un muro, per scoprire quante coppie di conigli discendessero da questa in un anno: per natura le coppie di conigli generano ogni mese un'altra coppia e cominciano a procreare a partire dal secondo mese dalla nascita.”
L. Fibonacci da Liber Abaci
16
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
I numeri di FibonacciI numeri di Fibonacci
Idea di base
1) fib(n)=1 se n=0 opp. n=1
2) fib(n)= fib(n-1) + fib(n-2) se n>1
17
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Successione di FibonacciSuccessione di Fibonacci
• Fib(n)=Fib(n-1)+Fib(n-2)• Fib(0)=0; Fib(1)=1;
int fibRic (int n) {
int ris;
if (n == 0) ris = 0;
else if (n == 1) ris = 1;
else ris = fibRic(n–1) + fibRic(n–2);
return ris;
}
18
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Un problema interessante:Un problema interessante:La torre di BrahmaLa torre di Brahma
19
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
La leggendaLa leggenda
• Narra la leggenda che all'inizio dei tempi, Brahma portò nel grande tempio di Benares, sotto la cupola d'oro che si trova al centro del mondo, tre colonnine di diamante e sessantaquattro dischi d'oro, collocati su una di queste colonnine in ordine decrescente, dal più piccolo in alto, al più grande in basso.
• E' la sacra Torre di Brahma che vede impegnati, giorno e notte, i sacerdoti del tempio nel trasferimento della torre di dischi dalla prima alla terza colonnina.
• Essi non devono contravvenire alle regole precise, imposte da Brahma stesso, che richiedono di spostare soltanto un disco alla volta e che non ci sia mai un disco sopra uno più piccolo.
• Quando i sacerdoti avranno completato il loro lavoro e tutti Quando i sacerdoti avranno completato il loro lavoro e tutti i dischi saranno riordinati sulla terza colonnina, la torre e il i dischi saranno riordinati sulla terza colonnina, la torre e il tempio crolleranno e sarà la fine del mondo. tempio crolleranno e sarà la fine del mondo.
20
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Le torri di HanoiLe torri di Hanoi
http://www.cs.cmu.edu/~cburch/survey/recurse/hanoi.html
Problema: spostare tutti i dischi dalla torre A alla torre B (usando la torre C come “supporto intermedio”) in modo che si trovino nello stesso ordine
21
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Le torri di HanoiLe torri di Hanoi
• Scriveremo una funzione ricorsiva che prende come parametro il numero del disco più grande che vogliamo spostare (da 0 a 5 come nel disegno)
• La funzione prenderà anche tre parametri che indicano: da quale asta vogliamo partire (source), a quale asta vogliamo arrivare (dest), l’altra asta, che possiamo usare come
supporto temporaneo (spare).
22
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
L’idea di baseL’idea di base
• Voglio spostare n anelli dal piolo sorgente, a quello destinazione, usando come appoggio il piolo ausiliario Devo quindi prima spostare n - 1 anelli
dal sorgente all'ausiliario, usando come appoggio il piolo destinazione
Poi sposto l'unico anello rimasto dal sorgente al piolo destinazione
Infine sposto gli n - 1 anelli che si trovano sull'ausilliario all'anello destinazione..
23
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
L’uso della ricorsioneL’uso della ricorsione
• Quando si spostano gli n - 1 anelli la funzione hanoi richiama se stessa, cioè effettua una chiamata ricorsiva, semplificando però il problema perché bisogna spostare un numero di anelli inferiore.
• In pratica, con la ricorsione il problema viene continuamente ridotto di complessità fino alla soluzione banale in cui rimane solo un anello, che viene semplicemente spostato nel piolo destinazione.
24
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Le torri di Hanoi: strategiaLe torri di Hanoi: strategia
Ridurremo il problema a quello di spostare 5 dischi dalla torre Calla torre B, dopo che il disco 5 è stato già messo nella posizione giusta
25
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Le torri di Hanoi: Le torri di Hanoi: pseudocodicepseudocodice
FUNCTION MoveTower(disk, source, dest, spare):IF disk == 0, THEN: move disk from source to destELSE: MoveTower(disk - 1, source, spare, dest) /* (Passo 1) */ move disk from source to dest //
/* (Passo 2) */ MoveTower(disk - 1, spare, dest, source) //
/* (Passo 3) */END IF
Nota: l’algoritmo aggiunge un caso base: quando il disco è il più piccolo (il numero 0). In questo caso possiamo muoverlo direttamente perché non ne ha altri sopra. Negli altri casi, seguiamo la procedura descritta per il disco 5.
26
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
CodiceCodice
void hanoi(int n, int sorgente, int destinazione, int aux) {
if (n==1)
printf("Sposto da %d a %d.\n",sorgente, destinazione);
else{
hanoi(n - 1, sorgente, aux, destinazione);
hanoi(1, sorgente, destinazione, aux);
hanoi(n - 1, aux, destinazione, sorgente);
}
}
27
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Esercizio: Massimo di un Esercizio: Massimo di un arrayarray
• Ideare un procedimento ricorsivo per calcolare il massimo di un array di interi
• Idea: max(vect[0 : N]) =max(vect[0],max(vect[1 : N]))
int max(int *array, int n){int maxs;if (n==1) return array[0]; /*Caso Array 1 elemento*/if (n==2){ /*Caso Base*/ if (array[0]>array[1]) return array[0]; else return array[1];}maxs = max(&array[1],n-1); /*Risolvi Problema Ridotto*/if (array[0]>maxs)return array[0];else return maxs;
}
28
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Fonti per lo studio + Fonti per lo studio + CreditsCredits• Fonti per lo studio
Introduzione alla programmazione in MATLAB, A.Campi, E.Di Nitto, D.Loiacono, A.Morzenti, P.Spoletini, Ed.Esculapio
• Capitolo 4– Particolare attenzione al 4.5
• Credits Prof. A. Morzenti Gianluca Palermo
29