DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
La Ricorsione
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 29 Maggio 2014
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• La ricorsione
Ricordate la sigla GNU
GNU = GNU is Not Unix
GNU = GNU is Not Unix
GNU = GNU is Not Unix
GNU = GNU is Not
GNU = GNU
2
L’induzione matematica
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si usa nelle definizioni e nelle dimostrazioni
• Definizione: numeri pari
 1) 0 è un numero pari
 2) se n è un numero pari anche n+2 è un numero pari
• Dimostrazione: dimostro che (2n)2=4n2
(distributività della potenza di 2 risp. alla moltiplicazione)
 1) n=1 : vero
 2) suppongo sia vero per k, lo dimostro per k+1:
(2(k+1))2=(2k+2)2=(2k)2+8k+4= (per hp di induzione) 4k2
+8k+4 = 4(k2 +2k+1) = 4(k+1)2
 1) è il passo base, 2) è il passo di induzione
3
Il tacchino induttivista
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Un tacchino induttivista viene allevato in una
fattoria del Maine (USA)
• Ogni giorno alle 7am Mr Jones porta il cibo al
tacchino induttivista
• Il tacchino segue il seguente ragionamento:
 Il giorno 1 Mr Jones mi ha portato il cibo @ 7am
 Ieri era il giorno “n” e Mr Jones mi ha portato il
cibo @ 7am
 Oggi è il giorno “n+1” ed il cibo è arrivato
 Tutti i giorni @l 7am Mr Jones mi porterà il cibo
• … Thanksgiving
4
Iterazione e ricorsione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Sono i due concetti informatici che
nascono dal concetto di induzione
5
Iterazione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• L’iterazione si realizza mediante la
tecnica del ciclo
• Il calcolo del fattoriale:
 0!=1
 n!=n(n-1)(n-2)….1 (realizzo un ciclo)
6
La ricorsione: definizione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
7
Scopo della programmazione ricorsiva
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
else
usa la ricorsione su dati ridotti
8
La ricorsione: che cos’è?
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
9
Un esempio classico
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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.
10
Altri esempi di ricorsione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• La sommatoria di una sequenza di numeri
• Fattoriale:
Fact(n)=n*Fact(n-1)
Fact(0)=1
• In arte e non solo…
11
Il calcolo del fattoriale
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
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
12
Il main del fattoriale
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
13
Il fattoriale iterativo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
14
Definizione ricorsiva del fattoriale
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
1) n!=1
se n=0
2) 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
15
Esempio di traccia
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
16
Il fattoriale ricorsivo
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Calcolo del Fattoriale in modo ricorsivo:
Fact(n)=n*Fact(n-1)
Fact(0)=1
fat=
1
FattRic(0)
fat=
1
FattRic(1)
fat=
2
FattRic(2)
fat=
6
FattRic(3)
n=3
main
17
Moltiplicazione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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;
}
18
Fibonacci
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
19
Il problema dei “conigli”
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
“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
20
I numeri di Fibonacci
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
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
21
Successione di Fibonacci
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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;
}
22
Un problema interessante:
La torre di Brahma
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
23
La leggenda
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
i dischi saranno riordinati sulla terza colonnina, la torre e il
tempio crolleranno e sarà la fine del mondo.
24
Le torri di Hanoi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
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
25
Le torri di Hanoi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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).
26
L’idea di base
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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..
27
L’uso della ricorsione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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.
28
Le torri di Hanoi: strategia
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Ridurremo il problema a quello di spostare 5 dischi dalla torre C
alla torre B, dopo che il disco 5 è stato già messo nella posizione
giusta
29
Le torri di Hanoi: pseudocodice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
FUNCTION MoveTower(disk, source, dest, spare):
IF disk == 0, THEN:
move disk from source to dest
ELSE:
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.
30
Codice
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
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);
}
}
31
Esercizio: Massimo di un array
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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;
}
32
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 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
33