Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 11 Ereditarietà in C++
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2 La ricorsione Corso di Informatica 2 a.a. 2003/04...
-
Upload
guido-marras -
Category
Documents
-
view
216 -
download
3
Transcript of Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2 La ricorsione Corso di Informatica 2 a.a. 2003/04...
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
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:
0 se)!1(
0 se1!
nnn
nn
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):
0 se)1(2
0 se1)(
nng
nng
definisce la funzionenng 2)(
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):
ne
nnn
n1
12!
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?
nninn
i
)1( 321!1
Qual è il significato algebrico dei
puntini?
Si se la regola è univoca
• Può una “regola di calcolo” definire una funzione?
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!
{
if (n == 0) return 1;
return n * fact(n - 1);
}
chiamata ricorsiva
caso di base
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(3) = ?
fact(2) = ?
2 * fact(1)
fact(1) = ?
1 * fact(0)
fact(0) = ?
fact(2) = ?
fact(1) = ?
fact(0) = ?
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(3) = ?
fact(2) = ?
2 * fact(1)
fact(1) = ?
1 * fact(0)
fact(0) = 1
fact(2) = ?
fact(1) = ?
fact(0) = 1
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(3) = ?
fact(2) = ?
2 * fact(1)
fact(1) = 1
1 * 1 fact(2) = ?
fact(1) = 1
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(3) = ?
fact(2) = 2
2 * 1
fact(2) = 2
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) … P(0)P(h) … m > h
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:
Per verificare che f sia definita ovunque dimostriamo (facilmente) per induzione completa su n, che
mnfmn )(.!
0 se))((,(
0 se)()(
nnsfnh
nngnf
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Massimo Comun Divisore
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
}
0 se)mod,MCD(
0 se),MCD(
mmnm
mnmn
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’ vuotom = (i + j)/2; // indice mediano in i..jif (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!{ int r = 1; while (n > 0) { r = r * n; --n; } return r;}
Come si fa a ricavarla?
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 == nr = 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
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
….
k
n
k
n
k
n 1
1
1
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); }
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)
n = 3
A B C
Ci vogliono 2n – 1 mosse per spostare
l’intera torre: e se n = 64?
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
A B C
n – 1 dischi
1. Sposta la torre in A – il disco alla base su C usando B
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
A B C
1. Sposta la torre in A – il disco alla base su C usando B
2. Sposta il disco in A su B
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
A B C
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
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Le torri di Hanoi (Lucas 1883)
A B C
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
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)
void f() { ... g(); ... }
void g() { ... f(); ... }
Nota: in C++ il protipo di g() deve precedere la definizione di f().
Sono mutuamente ricorsive quelle definizioni in cui due o più funzioni dipendono le une dalle altre:
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Ricorsione mutua (indiretta)
)2/(sin21cos
cos
sintan
altr. 0 ,2 se )2/(tan1
)2/tan(2sin
2
2
xx
x
xx
kxx
xx
Per il caso di base,
quando x è abbastanza piccolo 6sin
3xxx
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, ossia cresce circa come mn
2
2
2
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
Quando la ricorsione non serve
Consideriamo la sequenza di Fibonacci:
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?
2 se)1()2(
2 se)(
nnFibnFib
nnnFib
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
L’albero dei computi di FibRec
Fib(6)
Fib(4) Fib(5)
Fib(2) Fib(3)
Fib(0) Fib(1)
0 1
Fib(1)
1
Fib(2)
Fib(0)
0 1
Fib(1)
Fib(4)
Fib(2) Fib(3)
Fib(1)
0 1
Fib(1)
1
Fib(2)
Fib(0)
0 1
Fib(1)
Fib(0)
Fib(3)
1
Fib(2)
Fib(0)
0 1
Fib(1)
Fib(1)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 2
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