Ricorsione Ricorsione
Moreno Marzolla
Dipartimento di Informatica—Scienza e Ingegneria (DISI) Università di Bologna https://www.moreno.marzolla.name/
Libro cap. 5 (da 5.14 in poi)
Ricorsione 2
Ricorsione 3
Ricorsione
●
Definizione informale: la ricorsione è un procedimento
mediante il quale si definisce una entità in termini di se
stessa
Ricorsione 4
Ricorsione in natura broccolo romanesco
https://mimosadesigns.blogspot.it/2011/02/eating-fractals-and-stars.html
Ricorsione 5
Ricorsione in geometria:
Figure frattali
By Beojan Stanislaus, CC BY-SA 3.0,
https://commons.wikimedia.org/w/index.php?curid=8862246
By Niabot - Own work, CC BY 3.0,
https://commons.wikimedia.org/w/index.php?curid=7818920
Triangolo di Sierpinksi Spugna di Menger
Ricorsione 6
Ricorsione nelle arti visive
Immagine sulla confezione del cacao Droste (anno 1904); fonte Wikipedia
Copertina dell'album Ummagumma dei Pink Floyd (anno 1969); fonte Wikipedia
Ricorsione 7
Ricorsione
●
In matematica:
– Definizione di un concetto usando il concetto stesso
●
In C:
– Funzione che invoca (direttamente o indirettamente) se
stessa
Ricorsione 8
Esempio: successione di Fibonacci
●
Modello (non realistico) di crescita di una popolazione di conigli
– Una coppia all'inizio del primo mese
– A partire dalla fine del secondo mese di vita, ogni coppia produce un'altra
coppia alla fine di ogni mese
– I conigli non muoiono mai (!)
●
F(n) = coppie all'inizio del mese n
– F(1) = 1
– F(2) = 1
– F(n) = F(n – 1) + F(n – 2) per ogni n > 2
Leonardo Pisano detto Fibonacci (Pisa, 1170—Pisa, ca. 1250) http://it.wikipedia.org/wiki/Leonardo_FibonacciI conigli di Fibonacci
Ricorsione 11
Fibonacci in C
●
Metodo ricorsivo per il calcolo della successione di Fibonacci
– F(1) = 1
– F(2) = 1
– F(n) = F(n – 1) + F(n – 2) per ogni n > 2
int fib(int n) {
if (n <= 2) { return 1;
} else {
return fib(n - 1) + fib(n – 2);
}
}
Ricorsione 12
fib(3)
int fib(int n) {
if (n <= 2) { return 1;
} else {
return fib(n - 1) + fib(n – 2);
} }
fib(4)
return fib(3)+fib(2)
return fib(2)+fib(1)
return 1+fib(1)
return 1 return 1
return 1+1
return 1 return 2+1
fib(1)
fib(2)
return 2+fib(2)
fib(2)
………..
Ricorsione 13
Albero della ricorsione
fib(5)
fib(4) fib(3)
fib(3) fib(2) fib(2) fib(1)
fib(2) fib(1)
fib(4)
fib(3) fib(2) fib(2) fib(1)
fib(6)
Ricorsione 14
Costo computazionale
●
Sia T(n) il numero di chiamate alla funzione fib() che servono per calcolare fib(n)
– 1 chiamata per fib(1) → T(1) = 1
– 1 chiamata per fib(2) → T(2) = 1
– 3 chiamate per fib(3) → T(3) = 3
– 5 chiamate per fib(4) → T(4) = 5
– …
– T(n) = T(n - 1) + T(n - 2) + 1
fib(3)
fib(2) fib(1) fib(4)
fib(3) fib(2)
fib(2) fib(1)
Ricorsione 15
Quanto è grande T(n)?
●
Calcoliamo un limite inferiore per T(n)
●
Sfruttiamo il fatto che T(n) è non decrescente, cioè T(n) ≥ T(n - 1)
T (n) = T (n−1)+T (n−2)+1
≥ 2T (n−2)
≥ 4T (n−4)
≥ 8T (n−6)
≥ ...
≥ 2
kT (n−2 k)
≥ ...
≥ 2
⌊n/2⌋Ricorsione 16
Albero della ricorsione
fib(5)
fib(4) fib(3)
fib(3) fib(2) fib(2) fib(1)
fib(2) fib(1)
fib(4)
fib(3) fib(2) fib(2) fib(1)
fib(6)
●
La funzione fib(n) richiede un numero di chiamate ricorsive almeno esponenziale di n
– perché ricalcola più volte gli stessi valori
Ricorsione 17
Versione iterativa di fib(n)
●
Possiamo riscrivere
fib(n) in forma iterativa, ottenendo una versione molto più efficiente
– Non è sempre così: le funzioni ricorsive non
diventano automaticamente più efficienti se riscritte in modo iterativo
int fib(int n) {
if (n <= 2) { return 1;
} else {
int i, fn;
int fn1=1, fn2=1;
for (i=3; i<=n; i++) { fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
} }
Ricorsione 18
F(1) F(2)
Versione iterativa di fib(n)
1 1
fn2 fn1 fn
int fib(int n) {
if (n <= 2) { return 1;
} else {
int i, fn;
int fn1=1, fn2=1;
for (i=3; i<=n; i++) { fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
} }
Ricorsione 19
F(1)
Versione iterativa di fib(n)
1 2
fn2 fn1 fn
F(3) F(2)
1 2
i = 3 int fib(int n) {
if (n <= 2) { return 1;
} else {
int i, fn;
int fn1=1, fn2=1;
for (i=3; i<=n; i++) { fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
} }
Ricorsione 20
F(2)
3
Versione iterativa di fib(n)
1
fn2 fn1 fn i = 4
F(4) F(3)
2 3
int fib(int n) {
if (n <= 2) { return 1;
} else {
int i, fn;
int fn1=1, fn2=1;
for (i=3; i<=n; i++) { fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
} }
Ricorsione 21
F(3)
Versione iterativa di fib(n)
2
fn2 fn1 fn i = 5
5
F(5) F(4)
3 5
int fib(int n) {
if (n <= 2) { return 1;
} else {
int i, fn;
int fn1=1, fn2=1;
for (i=3; i<=n; i++) { fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
} }
Ricorsione 22
F(4)
Versione iterativa di fib(n)
3
fn2 fn1 fn i = 6
8
F(6) F(5)
5 8
int fib(int n) {
if (n <= 2) { return 1;
} else {
int i, fn;
int fn1=1, fn2=1;
for (i=3; i<=n; i++) { fn = fn1 + fn2;
fn2 = fn1;
fn1 = fn;
}
return fn;
} }
Ricorsione 23
La differenza tra un algoritmo di costo esponenziale e uno lineare
Fibonacci ricorsivo Intel Xeon 3.4GHz
anno 2015
Fibonacci iterativo C64 1MHz
anno 1982 fib(10) <0,001s 0,066s fib(20) <0,001s 0,150s
fib(30) 0,003s 0,233s
fib(40) 0,386s 0,300s
fib(50) 48,036s 0,400s
Ricorsione 24
Fattoriale
●
Metodo ricorsivo per il calcolo del fattoriale
– 0! = 1
– n! = n ´ (n – 1)! per ogni n > 0
int fatt(int n) { if (n == 0) {
return 1;
} else {
return n * fatt(n – 1);
} }
Ricorsione 25
Elevamento a potenza
●
potenza(a,n) calcola a
nper a > 0, n ≥ 0
– potenza(a, 0) = 1
– potenza(a, n) = a ´ potenza(a, n - 1), se n > 0
●
Esercizio: scrivere una versione ricorsiva di potenza() che funzioni anche quando n < 0
double potenza(double a, int n) { if (n == 0) {
return 1.0;
} else {
return a * potenza(a, n-1);
} }
Ricorsione 26
Ricorsione
●
Una funzione ricorsiva corretta ha le caratteristiche seguenti
– Include uno o più casi base, in cui il valore della funzione viene calcolato senza invocare la funzione
– Include una o più invocazioni ricorsive della funzione; nelle chiamate ricorsive generalmente si usano parametri che
"avvicinano" ai casi base
Ricorsione 27
Attenzione
●
La ricorsione deve terminare
– Per la successione di Fibonacci, la ricorsione termina nei casi base fib(1) e fib(2)
– Per il fattoriale, il caso base è fatt(0)
– Per l'elevamento a potenza, il caso base è potenza(a,0)
●
Ogni chiamata dovrebbe “avvicinare” al caso base
– Attenzione, però...
/* Per quali valori di n la funzione seguente termina? */
int fun(int n)
{ if ( n == 0 ) { return 1;
} else {
return (n + fun(n-2));
} }
Ricorsione 28
Le torri di Hanoi
Narra la leggenda che in un tempio in- diano si trovi una stanza contenente una lastra di bronzo con sopra tre pioli di diamante. Dopo la creazione
dell'universo, 64 dischi d'oro sono stati infilati in uno dei pioli in ordine decre- scente di diametro, con il disco più lar- go appoggiato al piano di bronzo. Da allora, i monaci del tempio si alternano per spostare i dischi dal piolo originario ad un altro piolo, seguendo le rigide regole di Brahma: i dischi vanno ma- neggiati uno alla volta, e non si deve mai verificare che un disco più largo sovrasti uno più piccolo sullo stesso piolo. Quando tutti i dischi saranno spostati su un altro piolo, l'universo avrà fine.
Fonte: George Gamow, One, two, tree...
infinity!, Dover Publications, 1947
Ricorsione 29
Le torri di Hanoi
●
Gioco matematico
– tre pioli
– n dischi di dimensioni diverse
– Inizialmente tutti i dischi sono impilati in ordine decrescente (più piccolo in alto) nel piolo di sinistra
●
Scopo del gioco
– Impilare in ordine decrescente i dischi sul piolo di destra
– Senza mai impilare un disco più grande su uno più piccolo
– Muovendo un disco alla volta
– Utilizzando se serve anche il piolo centrale
http://en.wikipedia.org/wiki/Tower_of_Hanoi
Ricorsione 30
Idea
Per spostare n dischi dal piolo src al piolo dst, usando tmp come appoggio
●
Se c'è un solo disco
– Spostalo da src a dst
●
Se ci sono n > 1 dischi
– Sposta gli n - 1 dischi in cima a src verso tmp, usando dst come appoggio
– Sposta un disco da src a dst
– Sposta n - 1 dischi in cima a
tmp verso dst, usando src come appoggio
src tmp dst
Ricorsione 31
Idea
Per spostare n dischi dal piolo src al piolo dst, usando tmp come appoggio
●
Se c'è un solo disco
– Spostalo da src a dst
●
Se ci sono n > 1 dischi
– Sposta gli n - 1 dischi in cima a src verso tmp, usando dst come appoggio
– Sposta un disco da src a dst
– Sposta n - 1 dischi in cima a
tmp verso dst, usando src come appoggio
src tmp dst
Ricorsione 32
Idea
Per spostare n dischi dal piolo src al piolo dst, usando tmp come appoggio
●
Se c'è un solo disco
– Spostalo da src a dst
●
Se ci sono n > 1 dischi
– Sposta gli n - 1 dischi in cima a src verso tmp, usando dst come appoggio
– Sposta un disco da src a dst
– Sposta n - 1 dischi in cima a
tmp verso dst, usando src come appoggio
src tmp dst
Ricorsione 33
Idea
Per spostare n dischi dal piolo src al piolo dst, usando tmp come appoggio
●
Se c'è un solo disco
– Spostalo da src a dst
●
Se ci sono n > 1 dischi
– Sposta gli n - 1 dischi in cima a src verso tmp, usando dst come appoggio
– Sposta un disco da src a dst
– Sposta n - 1 dischi in cima a
tmp verso dst, usando src come appoggio
src tmp dst
Ricorsione 34
Soluzione ricorsiva per le torri di Hanoi
/* hanoi.c */
void hanoi(int src, int dst, int tmp, int n) { if (n == 1) {
printf("Muovi da %d a %d\n", src, dst);
} else {
hanoi(src, tmp, dst, n-1)
printf("Muovi da %d a %d\n", src, dst);
hanoi(tmp, dst, src, n-1) } }
●
hanoi(1,3,2,n) sposta n dischi dal piolo 1 al piolo 3, usando il piolo 2 come appoggio
– n - 1 dischi da src a tmp
– 1 disco da src a dst
– n - 1 dischi da tmp a dst
http://en.wikipedia.org/wiki/Tower_of_Hanoi
Ricorsione 35
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 36
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 37
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 38
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 39
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 40
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 41
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 42
Esempio con 3 dischi
3 dischi da 1 a 3
2 dischi da 1 a 2 2 dischi da 2 a 3
1 disco da 1 a 3 1 disco da 3 a 2 1 disco da 2 a 1 1 disco da 1 a 3
1 → 3 1 → 2 3 → 2 1 → 3 2 → 1 2 → 3 1 → 3
1 2 3
Ricorsione 43
Numero di spostamenti
●
Quanti spostamenti sono necessari per risolvere il problema con n dischi?
– T(1) = 1
– T(n) = 2 T(n – 1) + 1 per n > 1
●
Domanda: Qual è la soluzione della ricorrenza?
–
Se i monaci eseguissero una mossa al secondo, per trasferire tutti i 64 dischi servirebbe un tempo pari a circa 127 volte l'età del nostro sole
void hanoi(int src, int dst, int tmp, int n) {
if (n == 1) {
printf("Muovi da %d a %d\n", src, dst);
} else {
hanoi(src, tmp, dst, n-1)
printf("Muovi da %d a %d\n", src, dst);
hanoi(tmp, dst, src, n-1)
} }
Ricorsione 47
Ricorsione mutua (indiretta)
●
Una funzione f1 ne chiama un'altra f2 (che ne chiama un'altra f3 …) che chiama f1
●
Es.: definiamo due funzioni pari e dispari che accettano un intero n ≥ 0 e ritornano 1 se n è pari (risp. dispari), 0 altrimenti
– Idea:
●
pari(n) = dispari(n - 1)
●
dispari(n) = pari(n - 1)
– Base della ricorsione:
●
pari(0) = 1
●
dispari(0) = 0
Ricorsione 48 /* pari-dispari.c : determina se un numero e' pari o dispari usando due funzioni mutuamente ricorsive */
#include <stdio.h>
/* Dichiarazione della funzione dispari */
int dispari(int n);
/* Definizione delle funzioni pari e dispari */
int pari(int n) { if (n == 0) {
return 1;
} else {
return dispari(n – 1);
} }
int dispari(int n) { if (n == 0) {
return 0;
} else {
return pari(n – 1);
} }
int main( void ) { int i;
for (i=0; i<10; i++) {
printf("%d pari=%d dispari=%d\n", i, pari(i), dispari(i));
}return 0;
}
Ricorsione 49
Ricorsione: cose da ricordare
●
Assicurarsi che ci sia sempre (almeno) un caso base
●
