G. Amodeo,
C. Gaibisso
Programmazione di Calcolatori
Lezione XXVII
La ricorsione
Programmazione di Calcolatori: la ricorsione
1
G. Amodeo,
C. Gaibisso
La ricorsione
• Definizione ricorsiva:
definizione di un oggetto (un insieme, una
struttura, una funzione, …) in termini della
definizione dell’oggetto stesso
• Comportamento ricorsivo
quello esibito da una classe di oggetti definibili
tramite due proprietà:
• un insieme di casi base
• un insieme di regole che riducono
qualsiasi caso a uno dei casi base
Programmazione di Calcolatori: la ricorsione
2
G. Amodeo,
C. Gaibisso
Le funzioni ricorsive
• Il fattoriale:
fatt : N    0  N 
1 if n  0

fatt ( n)  
 n  fatt ( n  1) otherwise
• I numeri di Fibonacci:
fib : N    0  N 
0 if n  0


fib( n)  
1 if n  1
 fibn  1  fib(n-2 ) otherwise

Programmazione di Calcolatori: la ricorsione
3
G. Amodeo,
C. Gaibisso
Le funzioni ricorsive
• Il calcolo:
fatt(5) = 5 * fatt(4)
=
= 5 * 4 * fatt(3)
=
= 5 * 4 * 3 * fatt(2)
=
= 5 * 4 * 3 * 2 * fatt(1)
=
= 5 * 4 * 3 * 2 * 1 * fatt(0) =
= 5*4*3*2*1*1
Programmazione di Calcolatori: la ricorsione
=
4
G. Amodeo,
C. Gaibisso
Le funzioni ricorsive
1 if n  0

fatt ( n)  
 n  fatt ( n  1) otherwise
// Nome e posizione del file:
//
Lezione_XXVII/fatt.c
// Descrizione del contenuto del file:
//
funzioni per il calcolo ricorsivo del fattoriale
// Descrizione della funzionalita' implementata:
//
calcola ricorsivamente il fattoriale di un intero positivo
// Tipo, nome e significato dei parametri della funzione:
//
int n: valore dell'argomento del fattoriale
// Tipo e significato del valore restituito:
//
int:
fattoriale del valore fornito in ingresso
int fatt(int n)
{
// il fattoriale di 0 e' 1
if (n == 0)
return(1);
// il fattoriale di n, con n diverso da, e' n per il fattoriale di n-1
return(n*fatt(n-1));
};
Programmazione di Calcolatori: la ricorsione
5
G. Amodeo,
C. Gaibisso
Le funzioni ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
6
G. Amodeo,
C. Gaibisso
Le funzioni ricorsive
0 if n  0

// Nome e posizione del file:

fib( n)  
1 if n  1
//
Lezione_XXVII/fibonacci.c
// Descrizione del contenuto del file:
 fibn  1  fib(n-2 ) otherwise

//
funzioni per il calcolo ricorsivo
//
della sequenza di fibonacci
// Descrizione della funzionalita' implementata:
//
calcola l’n-esimo numero della sequenza di fibonacci
// Tipo, nome e significato dei parametri della funzione:
//
int n: posizione del numero all'interno della sequenza di fibonacci
// Tipo e significato del valore restituito:
//
int:
l'n-esimo valore della sequenza di fibonacci
int fib(int n)
{
// il primo numero nella sequenza di fibonacci e' 0
if (n == 0)
return(0);
// il secondo numero nella sequenza di fibonacci e' 1
if (n == 1)
return(1);
// l'n-esimo numero nella sequenza di fibonacci, con n > 1, e' la somma
// dell'(n-1)-esimo e dell'(n-2)-esimo numero della stessa sequenza
return(fib(n-1)+fib(n-2));
};
Programmazione di Calcolatori: la ricorsione
7
G. Amodeo,
C. Gaibisso
Le funzioni ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
8
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Lista di valori di tipo T (LT):
empty  LT
LT  
if t  T and L  LT then t . L  LT
• Le liste:
tn.tn-1. … . t2. t1. empty
Programmazione di Calcolatori: la ricorsione
9
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• LLN?:
L = 100.8.4. 5. 28. empty LN ?
SI
100N e 8.4. 5. 28. empty LN ?
SI
8N e 4. 5. 28. empty LN ?
SI
4N e 5. 28. empty LN ?
SI
5N e 28. empty LN ?
28N e empty LN ?
SI
SI
SI
Programmazione di Calcolatori: la ricorsione
10
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• LLN?:
L = 100.8,5.4. 5. 28. empty LN ?
SI
100N e 8,5.4. 5. 28. empty LN ?
NO
8,5N e 4. 5. 28. empty LN ?
NO
Programmazione di Calcolatori: la ricorsione
11
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Qual è la somma degli elementi di LLN
(liste di naturali)?
somma : LN  N
if L  empty
0
somma(L)  
t  somma(L') if L  t.L'
Programmazione di Calcolatori: la ricorsione
12
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
0
somma(L)  
t  somma(L')
if L  empty
if L  t.L'
// Nome e posizione del file:
//
Lezione_XXVII/somma.c
// Descrizione del contenuto del file:
//
funzioni per il calcolo ricorsivo della somma degli elementi di
//
un vettore di naturali (codificata con un vettore di interi)
// Descrizione della funzionalita' implementata:
//
calcola ricorsivamente la somma degli elementi del vettore
// Tipo, nome e significato dei parametri della funzione:
//
int vett:
riferimento ad un vettore di interi
//
int dim:
dimensione del vettore
// Tipo e significato del valore restituito:
//
int: somma degli elementi del vettore
int somma(int *vett, int dim)
{
// se il vettore e' vuoto la somma vale 0
if (dim == 0)
return(0);
// la somma degli elementi di un vettore di dimensione non nulla
// e' pari al primo elemento del vettore + la somma degli
// elementi nella parte rimanente del vettore
return(vett[0] + somma(vett+1, dim-1);
};
Programmazione di Calcolatori: la ricorsione
13
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
14
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Ricerca ricorsiva di un elemento in LLT:
cerca : N  LN  true, false
if L  empty
 false

cerca(t, L)   true
if t  t'
 cerca(t, L') otherwise if L  (t'.L')

Programmazione di Calcolatori: la ricorsione
15
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
if L  empty
 false

cerca(t, L)   true
if t  t'

 cerca(t, L') otherwise if L  (t'.L')

// Nome e posizione del file:
//
Lezione_XXVII/cerca.c
// Descrizione del contenuto del file:
//
funzioni per la ricerca ricorsiva di un valore all'interno di una lista di
//
naturali (codificata con un vettore di interi)
// Descrizione della funzionalita' implementata:
//
ricerca ricorsivamente un valore all'interno di un vettore
// Tipo, nome e significato dei parametri della funzione:
//
int vett:
riferimento ad un vettore di interi
//
int dim:
dimensione del vettore
//
int val:
valore cercato
// Tipo e significato del valore restituito:
//
int: 1 se l'elemento è presente; 0 altrimenti
int cerca(int *vett, int dim, int val)
{
// se il vettore e' vuoto restituisce false
if (dim == 0)
return(0);
// se il primo elemento del vettore coincide con il valore cercato restituisce 1
if (vett[0] == val)
return(1);
// altrimenti cerca lo stesso valore all'interno del vettore privato del
// primo elemento
return(cerca(vett+1, dim-1, val, nro_call, lev_of_nest+1));
};
Programmazione di Calcolatori: la ricorsione
16
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
17
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• LLT è ordinata in modo strettamente
crescente?
ord  : LT  true, false
if L  empty
 true
 true
if L  t .empty

ord (L)  
if t1  t2
  false
if L  t1 .t2 . S'


 ord (t .L') otherwise
2
 
Programmazione di Calcolatori: la ricorsione
18
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
if L  empty
 true
 true
if L  t .empty


ord (L)  
if t1  t 2
  false
if L  t1 .t2 . S'

 ord (t 2 .L') otherwise


// Nome e posizione del file:
//
Lezione_XXVII/ordinata.c
// Descrizione del contenuto del file:
//
funzioni che verificano se una
//
lista di interi e' ordinata
// Descrizione della funzionalita' implementata:
//
verifica ricorsivamente se la lista e' ordinata
// Tipo, nome e significato dei parametri della funzione:
//
int vett:
riferimento ad un vettore di interi
//
int dim:
dimensione del vettore
// Tipo e significato del valore restituito:
//
int:
1 se la lista e' ordinata; 0 altrimenti
int ordinata (int *vett, int dim)
{
// se il vettore e' vuoto restituisce 1
if (dim == 0)
return(1);
// se la lista contiene un solo elemento restituisce 1
if (dim == 1)
return(1);
// se il primo elemento della lista e' superiore al secondo restituisce 0
if (vett[0] > vett[1])
return(0);
// altrimenti verifica il vettore privato del primo elemento
return(ordinata(vett+1, dim-1));
};
Programmazione di Calcolatori: la ricorsione
19
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
20
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
21
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Qual è il massimo di LLN?
max : LN  N   1
if L  empty
 1
t
if L  t .empty

max(L)  
if t  max(L')
 t
if L  t.L', L'  empty

 max(L') otherwise

Programmazione di Calcolatori: la ricorsione
22
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
if L  empty
 1
// Nome e posizione del file:
t
if L  t .empty
//
Lezione_XXVII/max_1.c

// Descrizione del contenuto del file:
max(L)  
t
if t  max(L')
//
funzioni per il calcolo ricorsivo

if L  t.L'

//
del massimo di una lista di
 max(L') otherwise

//
naturali
// Descrizione della funzionalita' implementata:
//
calcola ricorsivamente il massimo degli elementi del vettore
// Tipo, nome e significato dei parametri della funzione:
//
int vett:
riferimento ad un vettore di interi
//
int dim:
dimensione del vettore
// Tipo e significato del valore restituito:
//
int: massimo degli elementi del vettore
int max(int *vett, int dim)
{
// se il vettore e' vuoto il massimo è 0
if (dim == 0) return(0);
// se il vettore contiene un solo elemento il massimo e' l'elemento stesso
if (dim == 1) return(vett[0]);
// se il primo elemento e' maggiore del massimo della parte rimanente
// del vettore il massimo e' il primo elemento
if (vett[0] >= max(vett+1, dim-1))
return(vett[0]);
else
// altrimenti il massimo e' quello della parte rimanente del vettore
return(max(vett+1, dim-1))
};
Programmazione di Calcolatori: la ricorsione
23
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
24
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
25
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
if L  empty
 1
t
if L  t .empty

max(L)  
if t  max(L')
 t
if L  t.L'

 max(L') otherwise

// Nome e posizione del file:
//
Lezione_XXVII/max_1_o.c
// Descrizione del contenuto del file:
//
funzioni per il calcolo ricorsivo
//
del massimo di una lista di
//
naturali limitando il numero
//
delle chiamate ricorsive
// Descrizione della funzionalita' implementata:
//
calcola ricorsivamente il massimo degli elementi del vettore
// Tipo, nome e significato dei parametri della funzione:
//
int vett:
riferimento ad un vettore di interi
//
int dim:
dimensione del vettore
// Tipo e significato del valore restituito:
//
int: massimo degli elementi del vettore
int max(int *vett, int dim)
{
// definisce una variabile di appoggio per il massimo
int aux;
// se il vettore e' vuoto il massimo e' 0
if (dim == 0)
return(0);
// se il vettore contiene un solo elemento il massimo e' l'elemento stesso
if (dim == 1)
return(vett[0]);
Programmazione di Calcolatori: la ricorsione
26
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
// se il primo elemento e' maggiore del massimo della parte rimanente
// del vettore il massimo e' il primo elemento
if (vett[0] >= (aux=max(vett+1, dim-1)))
return(vett[0]);
else
// altrimenti il massimo e' quello della parte rimanente del vettore
return(max(vett+1, dim-1));
};
Programmazione di Calcolatori: la ricorsione
27
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
28
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
29
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Qual è il massimo di LLN?
max : LN  N   1
if L  empty
 1
t
if L  t .empty


max(L)  
 max(t .L') if t  t
1
1
2

if L  t1 .t2 . L'

 max(t 2 .L') otherwise

Programmazione di Calcolatori: la ricorsione
30
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
 1
t


max(L)  

 max(t1 .L') if t1  t2
 max(t .L') otherwise
2

if L  empty
if L  t .empty
// Nome e posizione del file:
//
Lezione_XXVII/max_2.c
// Descrizione del contenuto del file:
//
funzioni per il calcolo ricorsivo
if L  t1 .t2 . L'
//
del massimo degli elementi di
//
una lista di naturali
// Tipo, nome e significato dei parametri della funzione:
//
int vett:
riferimento ad un vettore di interi
//
int dim:
dimensione del vettore
// Descrizione della funzionalita' implementata:
//
calcola ricorsivamente il massimo degli elementi del vettore
// Tipo e significato del valore restituito:
//
int: massimo degli elementi del vettore
int max(int *vett, int dim)
{
// se il vettore e' vuoto il massimo è 0
if (dim == 0)
return(0);
// se il vettore contiene un solo elemento il massimo e'
// l'elemento stesso
if (dim == 1)
return(vett[0]);
Programmazione di Calcolatori: la ricorsione
31
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
// se il primo elemento e' maggiore del secondo, il massimo e' il massimo
// tra il primo elemento e gli elementi del vettore a partire dal terzo
if (vett[0] >= vett[1])
{
//scambia il primo elemento con il secondo
scambia(vett, vett+1);
return(max(vett+1, dim-1));
}
else
// altrimenti il massimo e' il massimo tra il II elemento e gli elementi
// del vettore a partire dal terzo
return(max(vett+1, dim-1));
};
Programmazione di Calcolatori: la ricorsione
32
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
33
G. Amodeo,
C. Gaibisso
Le strutture ricorsive
• Esecuzione:
Programmazione di Calcolatori: la ricorsione
34