Sistemi e Tecnologie
Informatiche
Ricorsione
Umberto Ferraro Petrillo
Nella lezione precedente …
… abbiamo imparato che:
• E’ possibile adoperare l’algoritmo di ricerca sequenziale per individuare
le occorrenze di un elemento all’interno di una lista
• Tale algoritmo può rivelarsi estremamente inefficiente poichè richiede
sino ad n confronti (dove n è pari alla taglia della lista) per individuare un elemento
• L’algoritmo di ricerca binaria migliora le prestazioni dell’algoritmo di ricerca
sequenziale a patto che l’elenco di input sia stato precedentemente ordinato
• L’algoritmo di ricerca binaria impiega sino a log(n) confronti per individuare
un elemento
In questa lezione …
… impareremo che:
• L’algoritmo di ricerca binaria adotta una strategia risolutiva che può
essere applicata anche ad altri problemi e che va sotto il nome di
ricorsione
• Esistono differenti tipi di ricorsione
• Non sempre l’approccio ricorsivo è quello migliore
Mistero …
Cerca elem nel vettore Voti[0 … n-1]
Sia Voti l’elenco di input, n la taglia dello stesso ed elem
l’elemento cercato
Dove si trovano i log(n)
confronti dell’algoritmo
di ricerca binaria???
Sia i l’indice dell’elemento attualmente considerato, inizialmente i = 0
Ripeti per n-1 volte o fino a che Voti[i] è uguale ad elem
Considera il prossimo elemento (i=i+1)
Se Voti[i] è uguale ad elem restituisci i altrimenti restituisci -1
Cerca elem nel vettore ordinato Voti[inf … sup]
Se l’array è vuoto (inf>sup) la ricerca termina (ritorna -1)
Considera l’elemento nella posizione centrale (med=(inf+sup)/2)
Se elem è uguale a Voti[med] la ricerca termina (ritorna med)
Altrimenti, se elem è minore di Voti[med] cerca elem nel vettore Voti[inf … med -1]
Altrimenti, cerca elem nel vettore Voti[med+1 … sup]
Ricerca binaria
Problema 1: Ricercare l’elemento 26 all’interno del vettore A[0…9]
0
1
2
3
4
5
6
7
8
9
19
21
24
25
25
26
27
28
28
29
Risposta problema 1: L’elemento si trova alla posizione 5!
Problema 2: Ricercare l’elemento 26 all’interno del vettore A[5…9]
5
6
7
8
9
26
27
28
28
29
Risposta problema 2: L’elemento si trova alla posizione 5!
Problema 3: Ricercare l’elemento 26 all’interno del vettore A[5…6]
5
6
26
27
Risposta problema 3: L’elemento si trova alla posizione 5!
Procedure ricorsive
• L’algoritmo di ricerca binaria è un tipico esempio di procedura ricorsiva
• Una procedura si dice ricorsiva quando all’interno della sua definizione
compare un riferimento alla procedura stessa (e.g. La funzione
PosizioneElemento(0,9,Voti,22) esegue al suo interno la funzione
PosizioneElemento(0,4,Voti,22))
• Affinchè l’esecuzione di una procedura ricorsiva finisca è prevista
l’esistenza di una condizione di terminazione (e.g. La ricerca binaria di un
elemento si arresta quando l’array è vuoto)
• La ricorsione ci consente la risoluzione di problemi complessi a parte da
problemi più elementari
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int PosizioneElemento(int inf, int sup, int Voti[], int elem) {
/* Effettua la ricerca binaria di elem tra i primi n elementi di Voti.
Il valore di ritorno e` -1 se elem non e` presente in Voti,
altrimenti e` l'indice della posizione di elem. */
• E’ possibile implementare
una procedura ricorsiva
in C/C++ attraverso le
chiamate a funzione
if ( inf>sup) // Verifichiamo se esistono elementi da considerare
return -1;
else{
int med = (int) (inf + sup) / 2;
• PosizioneElemento invoca
se stessa quando la taglia
dell’elenco in input è
diversa da zero
(condizione di ricorsione)
if (Voti[med] == elem)
return med;
// L’elemento è stato individuato
else
if (elem < Voti[med]) {
sup = med -1; // Cerchiamo nella porzione di sinistra
return PosizioneElemento(inf, sup, Voti, elem);
} else{
inf = med + 1; // Cerchiamo nella porzione di destra
return PosizioneElemento(inf, sup, Voti, elem);
}
}
} /* PosizioneElemento */
• PosizioneElemento
termina quando la taglia
dell’elenco in input è
zero
(condizione di terminazione)
Ricerca binaria
Sia dato in input il vettore Voti[0…9] e l’elemento 26
1 int PosizioneElemento(int inf, int sup, int Voti[], int elem) {
2
3 if ( inf>sup) // Verifichiamo se esistono ancora elementi
4 return -1;
5 else{
6 int med = (int) (inf + sup) / 2;
7
8 if (Voti[med] == elem)
9 return med;
// L’elemento è stato individuato
10 else
11 if (elem < Voti[med]) {
12
sup = med -1; // Cerchiamo nella porzione di sinistra
13
return PosizioneElemento(inf,sup,Voti, elem);
14 } else{
15
inf = med + 1; // Cerchiamo nella porzione di destra
16
return PosizioneElemento(inf, sup, Voti, elem);
17 }
18 }
19 } /* PosizioneElemento */
PosizioneElemento(0,9,Voti,26)
L’elemento centrale (Voti[4]) è minore
dell’elemento cercato, proseguiamo
la ricerca in Voti[5…9]
PosizioneElemento(5,9,Voti,26)
L’elemento centrale (Voti[7]) è maggiore
dell’elemento cercato, proseguiamo
la ricerca in Voti[5…6]
PosizioneElemento(5,9,Voti,26)
L’elemento centrale (Voti[5]) è uguale
all’elemento cercato, restituiamo
il suo indice 5
Ricorsione
Esistono due tipi di ricorsione:
• Ricorsione diretta:
All’interno della procedura A compare esplicitamente la chiamata
a se stessa
• Ricorsione indiretta
All’interno della procedura A viene invocata una seconda procedura
B che a sua volta invoca A
Ricorsione diretta
• Immaginiamo di disporre di un computer capace di sommare solo due
valori per volta
• Problema: Scrivere una funzione ricorsiva Somma capace di addizionare
un numero arbitrario di valori
• Osservazione: Somma(x,y,z,w) = Somma(x,y,z) + w
• Algoritmo risolutivo:
Somma(x1,…,xn-1,xn)
if (n > 2)
return Somma(x1,…,xn-1) + xn
else
if (n == 2)
return x1 + x2
else
return x1
Ricorsione diretta
• La funzione Somma sa addizionare esclusivamente due numeri
• Se i valori da sommare sono n, con n maggiore di 2, si sommano
“a parte” i primi n-1 numeri, il totale viene sommato al numero n-simo
Somma(7,3,9,6,2) = Somma(7,3,9,6) + 2 = 25 +2
Somma(7,3,9,6) = Somma(7,3,9) + 6 = 19 + 6 = 25
Somma(7,3,9) = Somma(7,3) + 9 =
Somma(7,3) = 7 + 3 =
10
10 + 9 = 19
Ricorsione indiretta
• Immaginiamo di disporre di un calcolatore incapace di operare divisioni
• Problema: Ideare una funzione ricorsiva Pari capace di dirci se un numero
è pari o meno
• Osservazione: x è pari se e solo se x-1 è dispari
• Algoritmo risolutivo:
Pari(x)
if x == 0
return true
else
return Dispari(x-1)
Dispari(y)
if y == 0
return false
else
return Pari(x-1)
Ricorsione indiretta
• Dato x in input, la funzione Pari restituisce vero se e soltanto se la
funzione Dispari(x-1) restituisce vero
• Dato y in input, la funzione Dispari restituisce vero se e soltanto se la
funzione Pari(y-1) restituisce vero
• Pari(0) restituisce vero
• Dispari(0) restituisce falso
Pari(5)
è vero se e solo se Dispari(4) è vero
Dispari(4) è vero se e solo se Pari(3) è vero
Pari(3)
è vero se e solo se Dispari(2) è vero
Dispari(2) è vero se e solo se Pari(1) è vero
Pari(1)
è vero se e solo se Dispari(0) è vero
Dispari(0) è falso
Numeri Fibonacci
I numeri di Fibonacci provengono da una successione numerica definita
dalla seguente relazione:
• Fib(n) = Fib(n-1) + Fib(n-2)
• Fib(0) = 1
• Fib(1) = 1
E.g.,
Fib(2) = Fib(1) + Fib(0) = 1 + 1 = 2
Fib(6) = Fib(5) + Fib(4) = Fib(4) + Fib (3) + Fib(4) = … = 13
Numeri Fibonacci
Calcolare il numero di Fibonacci associato a 5
Fib(5)
Fib(4)
Fib(3)
Fib(1)
Fib(2)
Fib(0)
Fib(1)
Fib(2)
Fib(0)
Fib(1)
Fib(3)
Fib(1)
Fib(0)
Fib(2)
Fib(1)
Numeri Fibonacci
• La strategia ricorsiva non sempre è quella migliore
• Nel caso dei numeri di Fibonacci essa si rivela inefficace poichè
costringe a ricalcolare numerose volte gli stessi risultati
• Il numero di esecuzioni della procedura Fibonacci calcolata sul valore n
è circa 2n
Numeri Fibonacci –
strategia iterativa
• Introduciamo un array Fib di taglia n per memorizzare il
valore dei numeri di Fibonacci già calcolati
Fib(5)
• Sia dato un numero x in input (e.g., 5)
• Calcoleremo il numero di Fibonacci associato ad x a
partire dagli elementi più piccoli, memorizzando e
riutlizzando i valori già calcolati
Fib(4)
Fib(3)
Fib(2)
Fib(1)
Fib(0)
Esercizio
• Immaginiamo di disporre di un calcolatore capace esclusivamente di
sommare o sottrarre 1 ad un qualsiasi valore numerico
• Problema: Come è possibile implementare la somma di una coppia di
numeri qualsiasi?
• E.g.,
22 + 49?