La ricorsione
Corso di Informatica 2
a.a. 2003/04
Lezione 2
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Circoli viziosi
Se in una definizione ciò che viene definito
(definiendum) è usato per definire (nel
definiens), la definizione è circolare:
Che cos’è un
“gavagai”?
Un gavagai è un
gavagai che salta
e balla
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Circoli virtuosi: i naturali
Tuttavia ci sono definizioni circolari che sono
perfettamente accettabili:
1. 0  N
2. se n  N allora (n + 1)  N
3. null’altro è in N
definisce l’insieme
N = {0, 0 +1, 0 + 1 + 1, 0 + 1 + 1 + 1, …}
= {0, 1, 2, 3, … }
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Circoli virtuosi: le stringhe
Sia V = {a, b, c, …} un insieme (finito) di simboli: il
vocabolario. Allora l’insieme V* delle stringhe su V
è definito:
1.   V* (la stringa vuota)
2. se a  V e   V* allora a  V*
3. null’altro è in V*.
V* = {, a, b, c, …, aa, ab, ac, … ba, bb, bc, …}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Circoli virtuosi: le liste
Sia T un tipo di dati; definiamo il tipo List(T) delle
liste, o sequenze finite, di dati di tipo T:
1. nil : List(T) (la lista vuota)
2. se d : T e l : List(T) allora Cons(d, l) : List(T)
3. null’altro ha tipo List(T).
nil, Cons(d1, nil), Cons(d2, Cons(d1, nil)), … : List(T)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Circoli virtuosi
Come mai la definizione di N è accettabile?
1. Perché ci fornisce un metodo (il successore)
per generare tutti i naturali a partire da un
elemento di base (lo zero)
2. Perché ci fornisce un criterio per verificare se
un certo oggetto è un numero naturale:
“n è naturale se è 0 oppure se è il successore di
un naturale”
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Definizioni ricorsive
Non solo certi insiemi, ma anche certe
funzioni sono definite in modo circolare, che
diremo ricorsivo:
1
se n  0

n! 
n  (n  1)! se n  0
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Definizioni ricorsive
Un modo per convincersi che una definizione
ricorsiva individui una funzione è di cercare una
forma equivalente esplicita (non ricorsiva):
1
se n  0

g ( n)  
2  g (n  1) se n  0
definisce la funzione
g ( n)  2 n
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Definizioni ricorsive
Ma questo non è sempre possibile: nel caso
del fattoriale il meglio che si sa fare è fornire
una formula esplicita approssimata (formula
di Stirling):
n
n! 2n  
e
n

 1 
1    
 n 

Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Regole di calcolo
Interpretiamo allora la definizione di n! come
una regola di calcolo:
6! =
=
=
=
=
=
=
=
6  5!
6  5  4!
6  5  4  3!
6  5  4  3  2!
6  5  4  3  2  1!
6  5  4  3  2  1  0!
6543211
720
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Alcuni dubbi
• Perché questa definizione esplicita non è
considerata?
Qual è il significato
n
n!  i  1  2  3    (n  1)  n
i 1
algebrico dei
puntini?
• Può una “regola di calcolo” definire una
funzione?
Si se la regola è
univoca
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Il programma “fattoriale”
long fact (long n)
// pre: n intero positivo
// post: ritorna n!
caso di base
{
if (n == 0) return 1;
return n * fact(n - 1);
}
chiamata ricorsiva
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Valutazione di funzioni ricorsive con
l’uso di una pila
fact(3) = ?
3 * fact(2)
fact(2) = ?
2 * fact(1)
fact(1) = ?
1 * fact(0)
fact(0) = ?
fact(0) = ?
fact(1) = ?
fact(2) = ?
fact(3) = ?
Pila domande/risposte
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Valutazione di funzioni ricorsive con
l’uso di una pila
fact(3) = ?
3 * fact(2)
fact(2) = ?
2 * fact(1)
fact(1) = ?
1 * fact(0)
fact(0) = 1
fact(0) = 1
fact(1) = ?
fact(2) = ?
fact(3) = ?
Pila domande/risposte
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Valutazione di funzioni ricorsive con
l’uso di una pila
fact(3) = ?
3 * fact(2)
fact(2) = ?
2 * fact(1)
fact(1) = 1
1 * 1
fact(1) = 1
fact(2) = ?
fact(3) = ?
Pila domande/risposte
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Valutazione di funzioni ricorsive con
l’uso di una pila
fact(3) = ?
3 * fact(2)
fact(2) = 2
2 * 1
fact(2) = 2
fact(3) = ?
Pila domande/risposte
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Valutazione di funzioni ricorsive con
l’uso di una pila
fact(3) = 6
3 * 2
fact(3) = 6
Pila domande/risposte
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Insertsort ricorsivo
void Insertsort (int v[], int n)
// post: v[0..n-1] e’ ordinato in senso non
//
descrescente
{
if (n < 2) return; // v[0..n-1] e’ ordinato
// n >= 2
Insertsort(v, n-1);
// ex ip. ind. v[0..n-2] e' ordinato
int i, temp = v[n-1];
for (i = n-1; i > 0 && v[i-1] > temp; i--)
v[i] = v[i-1];
v[i] = temp;
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Induzione completa
Se  è un ordine ben fondato, possiamo rafforzare il
principio di induzione sui naturali nel seguente
modo:
Base: P(0)
Passo:  m[n < m.P(n)  P(m)]
P(m)
m>h
…
P(h)
…
P(0)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Funzioni ricorsive “induttive”
Siano g ed h funzioni totali, ed s tale che 0  s(n) < n
per ogni n; allora la funzione f è definita e totale:
g ( n)
se n  0

f ( n)  
h(n, f ( s(n)) se n  0
Per verificare che f sia definita ovunque dimostriamo
(facilmente) per induzione completa su n, che
n!m. f (n)  m
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Massimo Comun Divisore
n
se m  0

MCD( n, m)  
MCD( m, n mod m) se m  0
int MCD(int n, int m)
// pre: n, m positivi non entrambi nulli
// post: ritorna il massimo comun divisore di n ed m
{
if (m == 0) return n;
return MCD(m, n % m);
// n % m == n mod m
// definito per ind. completa sul secondo parametro
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricursione sulla dimensione
Un esempio di ricorsione basata sull’induzione completa è
quello di funzioni ricorsive sulla dimensione:
bool BinSearchRic (int v[], int i, int j, int x)
// pre: v[i..j] e’ ordinato in modo crescente
// post: ritorna true sse x in v[i..j]
{
int m;
if (i > j) return false; // v[i..j] e’ vuoto
m = (i + j)/2; // indice mediano in i..j
if (x == v[m]) return true;
if (x < v[m]) return BinSearch(v, i, m-1, x);
return Binsearch(v, m+1, j, x);
// in entrambi i casi le chiamate ricorsive sono
// su intervalli < 1/2 dell’intervallo i..j
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione ed iterazione
La funzione fact poteva essere iterativa:
long factiterativo (long n)
// pre: n intero positivo
// post: ritorna n!
Come si fa a
{
ricavarla?
int r = 1;
while (n > 0)
{
r = r * n;
--n;
}
return r;
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione ed iterazione
• La ricorsione va all’indietro (risale ai precedenti valori):
fact(n)  fact(n-1)  fact(n-2) …
e poi in avanti (ricombina insieme i valori ottenuti):
1 * 1  1 * 2  2 * 3  6 * 4
• L’iterazione va solo in avanti (accumula il risultato):
r = 1
r = r * n // r == n
r = r * n-1 // r == n * (n-1)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione in coda
Si parla di ricorsione in coda quando vi è una sola
chiamata ricorsiva, la quale è l’ultima istruzione che
la funzione esegua.
void stampavettore(int v[], int i, int n)
// pre: v e' un vettore di n interi
// post: stampa nell'ordine gli el. di v[i..n-1]
{
if (i < n)
{ cout << v[i] << " ";
stampavettore(v, i+1, n);
}
chiamata ricorsiva in coda
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Uso della funzione ausiliare
La funzione stampavettore ha un parametro in più, i, che
andrebbe eliminato:
void stampavettoreaux(int v[], int i, int n)
// la precedente funzione “stampavettore” ricorsiva
{
if (i < n)
{ cout << v[i] << " ";
stampavettoreaux(v, i+1, n);
}
}
void stampavettore(int v[], int n)
// pre: v e' un vettore di n interi
// post: stampa nell'ordine gli el. di v[0..n-1]
{
stampavettoreausiaux(v, 0, n); }
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione in coda
Poiché procede in un unico verso, una ricorsione in
coda è un’ iterazione camuffata:
void stampavettoreiterativa(int v[], int n)
// pre: v e' un vettore di n interi
// post: stampa nell'ordine gli el. di v[i..n-1]
{
for (int i = 0; i < n; i++)
cout << v[i] << " ";
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione non in coda
long coeffbin(long n, long k)
// pre: n,k interi positivi con n >= k
// post: calcola il coefficiente
//
binomiale (n k)
{
if (k == 0 || k == n) return 1;
return
coeffbin(n-1,k-1) + coeffbin(n-1,k); }
1
1
1
1
2
1
1
3
3
1
1
4
6
4
….
1
 n   n  1  n  1
   
  

 k   k  1  k 
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
Dati tre pioli, su cui sono inseriti n dischi di diametro
crescente, spostare la torre da un piolo sorgente (A) ad uno
destinazione (B) , sfruttando un piolo d’appoggio (C),
muovendo un disco alla volta, senza mai sovrapporre un disco
più grande ad uno più piccolo.
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
Ci vogliono 2n – 1
mosse per spostare
l’intera torre:
e se n = 64?
n=3
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
1. Sposta la torre in A – il disco alla base su C usando B
A
B
C
n–1
dischi
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
1. Sposta la torre in A – il disco alla base su C usando B
2. Sposta il disco in A su B
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
1. Sposta la torre in A – il disco alla base su C usando B
2. Sposta il disco in A su B
3. Sposta la torre in C (di n – 1 dischi) su B usando A
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
1. Sposta la torre in A – il disco alla base su C usando B
2. Sposta il disco in A su B
3. Sposta la torre in C (di n – 1 dischi) su B usando A
A
B
C
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
void Hanoi (Torre sor, Torre des, Torre aux)
// sor == sorgente, des == destinazione,
// aux == ausiliaria
{
if (Sopra(sor) == NULL)
// Sopra(t)== la torre su t – la base
muovidisco(sor, des);
else {
Hanoi (Sopra(sor), aux, des);
muovidisco(sor, des);
Hanoi (aux, Sopra(des), sor);
}
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione mutua (indiretta)
Sono mutuamente ricorsive quelle definizioni in cui
due o più funzioni dipendono le une dalle altre:
void f() { ... g(); ... }
void g() { ... f(); ... }
Nota: in C++ il protipo di g() deve precedere la definizione di f().
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione mutua (indiretta)
2 tan( x / 2)
sin x 
se x    2k , 0 altr.
2
1  tan ( x / 2)
sin x
tan x 
cos x
cos x  1  2 sin 2 ( x / 2)
Per il caso di base,
quando x è abbastanza piccolo
x3
sin x  x 
6
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione annidata
Infrequente (ed insensata) in pratica, consente di
definire funzioni con tasso di crescita molto elevato:
long Ackermann (long n, long m)
{ if (n == 0) return m+1;
if (n > 0 && m == 0) return Ackermann(n-1, 1)
return Ackermann(n-1, Ackermann(n, m-1));
}
Questa funzione ha un tasso di crescita iperesponenziale,
2
ossia cresce circa come
2  n m
2


Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Quando la ricorsione non serve
Consideriamo la sequenza di Fibonacci:
n
se n  2

Fib(n)  
 Fib(n  2)  Fib(n  1) se n  2
Questa è generata dalla funzione ricorsiva:
int FibRec(int n)
{
if (n < 2) return n;
return FibRec(n-2) + FibRec(n-1);
}
Quante sono le addizioni? Quante le chiamate?
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
L’albero dei computi di FibRec
Fib(6)
Fib(4)
Fib(2)
Fib(5)
Fib(3)
Fib(0) Fib(1) Fib(1)
0
1
Fib(3)
Fib(2)
Fib(1)
Fib(4)
Fib(2)
Fib(2)
1 Fib(0) Fib(1) 1 Fib(0) Fib(1)
0
1
0
1
Fib(3)
Fib(0) Fib(1) Fib(1) Fib(2)
0
1
1 Fib(0) Fib(1)
0
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
1
Quante addizioni in FibRec(n)?
n
Fib(n)
Addizioni
Chiamate
6
8
12
25
8
21
33
67
10
55
88
177
15
610
986
1973
20
6765
10945
21891
30
832040
1346268
2692537
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Una versione iterativa
La sequenza di Fibonacci si calcola in modo più efficiente
iterativamente:
int FibIter (int n)
{
int a, b, c, i;
if (n < 2) return n;
a = 1; b = 0;
for(i = 2; i <= n; i++)
// inv. a = Fib(i-1), b = Fib(i-2)
{
c = a; a = b + a; b = c;}
return a;
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Riassumendo
• Una definizione circolare è sensata se induttiva
• Linguaggi come il C++ ammettono definizioni
ricorsive di funzioni
• La ricorsione è riducibile all’iterazione:
direttamente se di coda, con l’uso di una pila nel
caso generale
• La ricorsione è spesso più chiara (e astratta)
dell’iterazione, ma può essere molto inefficiente
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2