ppt

1
Per illustrare il concetto di ricorsione ricordiamo un metodo
matematico per fare dimostrazioni: l’induzione.
Mostreremo di seguito alcune dimostrazioni per induzione e
i corrispondenti algoritmi ricorsivi.
2
DIMOSTRAZIONE PER INDUZIONE
La dimostrazione per induzione è una tecnica per provare che un
asserto S(n) vale per tutti gli interi n maggiori di un certo limite
inferiore.
Supposto vero l’asserto la dimostrazione consiste in:
• individuare un caso base, il minimo valore di n, diciamo k, per cui
si dimostra l’asserto S(k)
• dimostrare il passo induttivo, cioè che per ogni n  k , dove S(k) è
la base induttiva, S(n) implica S(n+1) o equivalentemente supposto
vero S(n) dimostrare che è vero S(n+1).
3
DIMOSTRAZIONE PER INDUZIONE
SOMMA DEI PRIMI N INTERI POSITIVI
N  ( N  1)
i

2
i 0
N
Vogliamo dimostrare che S(n):
caso base
Poniamo N=1 avremo
a)
0
i  0
che è quindi dimostrato vero
i 0
passo induttivo
Dobbiamo ora dimostrare che
( N  1)  ( N  2)
i

2
i 0
N 1
b)
Possiamo scrivere
N  ( N  1)
i  i  ( N  1) 
 ( N  1) 

2
i 0
i 0
N  ( N  1)  2  ( N  1) ( N  1)  ( N  2)

q.e.d.
2
2
N 1
N
4
DEFINIZIONE DI ALGORITMO RICORSIVO
Diremo che un algoritmo è ricorsivo se risolve il problema a cui è
riferito utilizzando la soluzione dello stesso problema ottenuta ad
un livello inferiore cioè in un caso più semplice.
5
Una funzione ricorsiva per risolvere un problema per prima cosa
deve essere in grado di risolvere i casi più semplici, detti casi-base:
in queste situazioni la funzione ricorsiva termina e restituisce una
soluzione.
Nelle altre situazioni, la funzione ricorsiva, deve poter dividere il
problema in sotto problemi simili a quello di partenza e da esso
differenti solo per le dimensioni.
In tal caso la funzione ricorsiva, richiama una copia di se stessa e
riprende la computazione.
Questa operazione è detta chiamata ricorsiva della funzione.
6
Nel lucido seguente si mostra come opera una funzione ricorsiva in
presenza di un problema di cui si conosca la soluzione per almeno un
caso semplice (caso base) e la sua trasformazione da una
rappresentazione semplice ad un’altra di dimensioni maggiori.
7
COME FUNZIONA LA RICORSIVITA’
problema(p1 ,…., pk )
caso base ? NO allora applica
Applica la soluzione a
problema(p’1 ,…., p’k )
Applica la soluzione a
problema(p”1 ,…., p”k )
caso base ? NO allora applica
caso base ? NO allora applica
problema(p*1 ,…., p*k )
caso base ? SI allora applica
la soluzione a
Dove (pi1 ,…., pik ) sono problemi ridotti del problema precedente
8
In pseudo codice potremmo dire che:
if i parametri fanno riferimento a un caso base
risolvi il problema
else
usa i valori dei parametri per un problema ridotto
CHIAMA LA FUNCTION PER
RISOLVERE IL PROBLEMA RIDOTTO
Possiamo dire che in questo modo viene applicato il metodo del
DIVIDE ET IMPERA
9
Un algoritmo iterativo consiste in un unico processo che ripete le stesse
identiche operazioni molte volte.
Un algoritmo ricorsivo consiste in un numero finito di processi aperti
uno dopo l’altro e posti in uno stack. Non appena si chiude un processo
subito si scende nello stack e si chiude il processo immediatemente
seguente e così via di seguito.
problema(p*1 ,…., p*k )
problema(p”1 ,…., p”k )
problema(p’1 , …., p’k )
problema(p1 ,… . ., pk )
10
Per scrivere un algoritmo ricorsivo bisogna soddisfare le seguenti
condizioni:
1. Esiste almeno un caso base la cui soluzione è banale
2. Tutti i sottoproblemi devono poter essere risolti in termini di versioni
ridotte di uno stesso problema
3. Le azioni applicate per la soluzione di un problema ridotto portano
sempre alla soluzione di un problema più grande
4. In funzione di quanto sia grande il problema iniziale deve essere
sempre possibile trovare almeno un caso base nel corso della
elaborazione del problema originale.
11
Riportiamo di seguito una serie di esempi che illustrano l’uso
della ricorsività in maniera adeguata.
Iniziamo con una funzione che calcola la somma dei primi N
numeri interi positivi.
A tal fine si ricordi la dimostrazione per induzione introdotta
precedentemente.
12
Sommatoria dei primi N interi positivi
1. La somma dei primi 0 interi positivi vale 0.
2. La somma dei primi N interi positivi è uguale alla somma dei
primi N-1 interi più N.
int Sum(int N)
{
if N=0
Sum =0;
else
Sum =N+ Sum(N-1);
};
Un processo come quello qui descritto si dice per accumulazione.13
Sommatoria dei primi N interi positivi
La rappresentazione nello stack del processo ricorsivo è illustrata
di seguito.
Come si può osservare vengono aperti tanti processi fin quando
non si raggiunge il caso base.
A questo punto ogni processo viene chiuso inviando il risultato
raggiunto al processo che lo precede nello stack.
Caso base
int Sum(int N)
{
if N=0
Sum =0;
else
Sum =N+ Sum(N-1);
};
1+ Sum(0)
Sum =1
2+Sum(1)
Sum =3
3+ Sum(2)
Sum =6
4+ Sum(3)
Sum =10
5+ Sum(4)
Sum =15
Sia N=5
Inizio del
processo
14
Risultato
Codice della funzione che calcola la somma dei primi N numeri
interi positivi.
// Somma ricorsiva
#include <iostream>
using namespace std;
// PROTOTIPI
int somma(int ,int);
// DEFINIZIONI
int somma(int N)
{
if (N==0)
return 0;
else
return somma((N-1))+N ;
}
// MAIN
int main ()
{
int N;
cout<<" A partire da 1 fino a che numero vuoi fare la somma? ";
cin>>N;
cout<<"\n La somma dei primi "<<N<<" e' pari a "<<somma(N)<<endl;
system("pause");
}
15
Quando si applica un processo ricorsivo bisogna assicurarsi che le
variabili riguardanti la ricorsione siano passate per valore mentre le
variabili in cui eventualmente si accumulano dati, esempio il numero
di passi totale, vanno passate per riferimento.
16
Ad esempio se vogliamo mostrare il risultato del calcolo della
somma parziale dei primi N interi positivi diciamo ogni M passi
è necessario introdurre una variabile che tenga conto delle varie
somme parziali e che va chiamata per valore.
Di seguito mostriamo il codice.
17
// PROTOTIPO
void somma(int ,int, int&);
/
/ MAIN
int main ()
{
int s=0;
somma(N,M,s);
cout<<"\n La somma dei primi "<<N<<" numeri mostrata ogni "<<M<<
" intervalli e' pari a "<<s<<endl;
system("pause");
}
// DEFINIZIONE
void somma(int N,int M, int &sum)
{
if (N==0) sum=0;
else
SommaRic
{
somma((N-1),M,sum);
sum=sum+N;
if ((N % M)==0)
cout<<"\n La somma dei primi "<<N<<" numeri vale "<<sum<<endl;
}
18
return ;
}
Un altro esempio di algoritmo ricorsivo è quello che valuta la
somma delle potenze di 2 da 0 a N.
Di seguito mostriamo prima la dimostrazione per induzione del
calcolo e quindi l’algoritmo ricorsivo che ad esso si ispira.
19
DIMOSTRAZIONI PER INDUZIONE
SOMMA DI POTENZE DI 2
Vogliamo dimostrare che:
n
i
n 1
2

2
1

i 0
caso base
Poniamo n=0 avremo
0
2
i
21  1
che è quindi dimostrato vero
i 0
20  1
20
passo induttivo
Dobbiamo ora dimostrare che
n 1
i
n 2
2

2
1

i 0
n
i
n 1
2

2
1

Supposto sia vero
i 0
Il membro sinistro può essere riscritto come
n 1
n
i
n 1
2

2

2
 
i
i 0
a)
i 0
n
Avendo supposto vero l’asserto

2i  2 n 1  1
b)
i 0
Sostituiamo b) in a)
n 1
2
i 0
i
2 n 1  1  2 n 1  2 * 2 n 1  1  2 n  2  1
c.v.d.21
Algoritmo ricorsivo per calcolare
la somma delle potenze di 2 tra 0 e N
double SumPot(int N)
{
if (N==0)
return 1;
else
return pow(2,N)+SumPot(N-1);
}
22
Algoritmo ricorsivo:
Fare la somma delle potenze di 2 tra 0 e N
Caso base
1+ SumPot(0)
SumPot =1
2+SumPot (1)
SumPot =3
4+ SumPot (2)
SumPot =7
8+ SumPot (3)
SumPot =15
16+ SumPot (4)
SumPot =31
32+ SumPot (5)
SumPot =63
In fig. è mostrato
lo stack dei processi aperti
nel caso di N=5
Inizio del
processo
Risultato
23
In allegato è mostrato un codice che calcola:
La somma dei numeri interi tra 1 e N
Il valore di 2N
La somma delle potenze di 2i con 0<=i<=N
Allegato: sommaRic
24
ESERCIZI
Calcolare con una funzione ricorsiva le seguenti espressioni:
a)
b)
1 1 1 1 1 1 1
1
1
1
1
1
1
1
1
1
1
1
11