Sistemi e Tecnologie Informatiche

Ricorsione

Umberto Ferraro Petrillo

Nella lezione precedente …

… abbiamo imparato che:

• E’ possibile adoperare l’algoritmo di ricerca sequenziale per individuarele 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 ricercasequenziale a patto che l’elenco di input sia stato precedentemente ordinato

• L’algoritmo di ricerca binaria impiega sino a log(n) confronti per individuareun 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 eleml’elemento cercato

Sia i l’indice dell’elemento attualmente considerato, inizialmente i = 0

Ripeti per n-1 volte o fino a che Voti[i] è uguale ad elemConsidera 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]

Dove si trovano i log(n)confronti dell’algoritmodi ricerca binaria???

Ricerca binaria

19 24 25 25 26 27 28 28 2921

0 631 742 85 9

Problema 1: Ricercare l’elemento 26 all’interno del vettore A[0…9]

26 27 28 28 29

6 7 85 9

Problema 2: Ricercare l’elemento 26 all’interno del vettore A[5…9]

26 27

65

Problema 3: Ricercare l’elemento 26 all’interno del vettore A[5…6]

Risposta problema 3: L’elemento si trova alla posizione 5!

Risposta problema 2: L’elemento si trova alla posizione 5!

Risposta problema 1: 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

• E’ possibile implementareuna procedura ricorsivain C/C++ attraverso lechiamate a funzione

• PosizioneElemento invocase stessa quando la tagliadell’elenco in input èdiversa da zero(condizione di ricorsione)

• PosizioneElementotermina quando la tagliadell’elenco in input èzero(condizione di terminazione)

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. */

if ( inf>sup) // Verifichiamo se esistono elementi da considerare return -1;else{ int med = (int) (inf + sup) / 2;

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 */

123456789

1011121314151617181920212223

Ricerca binariaSia dato in input il vettore Voti[0…9] e l’elemento 26

PosizioneElemento(0,9,Voti,26)

L’elemento centrale (Voti[4]) è minoredell’elemento cercato, proseguiamo

la ricerca in Voti[5…9]

PosizioneElemento(5,9,Voti,26)

L’elemento centrale (Voti[7]) è maggioredell’elemento cercato, proseguiamo

la ricerca in Voti[5…6]

PosizioneElemento(5,9,Voti,26)

L’elemento centrale (Voti[5]) è ugualeall’elemento cercato, restituiamo

il suo indice 5

int PosizioneElemento(int inf, int sup, int Voti[], int elem) {

if ( inf>sup) // Verifichiamo se esistono ancora elementi return -1;else{ int med = (int) (inf + sup) / 2;

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 */

123456789

10111213141516171819

Ricorsione

Esistono due tipi di ricorsione:

• Ricorsione diretta: All’interno della procedura A compare esplicitamente la

chiamata a se stessa

• Ricorsione indirettaAll’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) = Somma(7,3,9) + 6 =

Somma(7,3,9) = Somma(7,3) + 9 =

Somma(7,3) = 7 + 3 =

25 +2

19 + 6 = 25

10 + 9 = 19

10

Somma(7,3,9,6,2)

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 trueelse return Dispari(x-1)

Dispari(y)if y == 0 return falseelse 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) è veroDispari(4) è vero se e solo se Pari(3) è vero Pari(3) è vero se e solo se Dispari(2) è veroDispari(2) è vero se e solo se Pari(1) è veroPari(1) è vero se e solo se Dispari(0) è veroDispari(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

Fib(5)

Fib(4)Fib(3)

Fib(1) Fib(2)

Fib(1)Fib(0)

Fib(3)

Fib(1) Fib(2)

Fib(0) Fib(1)

Fib(2)

Fib(0) Fib(1)

Calcolare il numero di Fibonacci associato a 5

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

Fib(5)

Fib(4)

Fib(3)

Fib(2)

Fib(1)

Fib(0)

• Introduciamo un array Fib di taglia n per memorizzare ilvalore dei numeri di Fibonacci già calcolati

• Sia dato un numero x in input (e.g., 5)

• Calcoleremo il numero di Fibonacci associato ad x apartire dagli elementi più piccoli, memorizzando eriutlizzando i valori già calcolati

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?