1

2

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.

3

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).

4

DIMOSTRAZIONE PER INDUZIONESOMMA DEI PRIMI N INTERI POSITIVI

Vogliamo dimostrare che S(n): a)

2

)1(

0

NNi

N

i

caso basePoniamo N=1 avremo che è quindi dimostrato vero0

0

0

i

i

Possiamo scrivere

2

)2()1(

2

)1(2)1(

)1(2

)1()1(

0

1

0

NNNNN

NNN

NiiN

i

N

i

q.e.d.

passo induttivoDobbiamo ora dimostrare che b)

2

)2()1(1

0

NNi

N

i

5

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.

6

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.

7

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.

8

COME FUNZIONA LA RICORSIVITA’

problema(p’1 ,…., p’k ) caso base ? NO allora applica

problema(p”1 ,…., p”k ) caso base ? NO allora applica

problema(p*1 ,…., p*k )

caso base ? SI allora applicala soluzione a

Applica la soluzione a

problema(p1 ,…., pk ) caso base ? NO allora applica

Applica la soluzione a

Dove (pi1 ,…., pi

k ) sono problemi ridotti del problema precedente

9

if i parametri fanno riferimento a un caso baserisolvi il problema

elseusa i valori dei parametri per un problema ridotto

CHIAMA LA FUNCTION PERRISOLVERE IL PROBLEMA RIDOTTO

Possiamo dire che in questo modo viene applicato il metodo del

DIVIDE ET IMPERA

In pseudo codice potremmo dire che:

10

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(p1 ,… . ., pk )

problema(p’1 , …., p’k )

problema(p”1 ,…., p”k )

problema(p*1 ,…., p*k )

11

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.

12

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.

13

int Sum(int N){

if N=0 Sum =0;else Sum =N+ Sum(N-1);};

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.

Un processo come quello qui descritto si dice per accumulazione.

14

int Sum(int N){ if N=0 Sum =0; else Sum =N+ Sum(N-1);

};

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.

5+ Sum(4) Sum =15

Sia N=5

4+ Sum(3)

3+ Sum(2)

2+Sum(1)

1+ Sum(0) Sum =1

Sum =3

Sum =6

Sum =10

Inizio del processo

Caso base

Risultato

15

// Somma ricorsiva#include <iostream>

using namespace std;// PROTOTIPIint somma(int ,int);

// MAINint 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");}

// DEFINIZIONI

int somma(int N){ if (N==0) return 0; else return somma((N-1))+N ;}

Codice della funzione che calcola la somma dei primi N numeri interi positivi.

16

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.

17

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.

18

// PROTOTIPOvoid somma(int ,int, int&);// MAINint 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"); }

// DEFINIZIONEvoid somma(int N,int M, int &sum){ if (N==0) sum=0; else { somma((N-1),M,sum); sum=sum+N; if ((N % M)==0) cout<<"\n La somma dei primi "<<N<<" numeri vale "<<sum<<endl; } return ; }

SommaRic

19

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.

20

DIMOSTRAZIONI PER INDUZIONE

Vogliamo dimostrare che:

122 1nn

0i

i

caso basePoniamo n=0 avremo che è quindi dimostrato vero

12

122

0

10

0i

i

SOMMA DI POTENZE DI 2

21

Il membro sinistro può essere riscritto come

Avendo supposto vero l’asserto

Sostituiamo b) in a)

1nn

0i

i1n

0i

i 222

a)

122 1nn

0i

i

b)

1212*22122 21111

0

nnnnn

i

i

passo induttivoDobbiamo ora dimostrare che 122 2n

1n

0i

i

c.v.d.

122 1nn

0i

i

Supposto sia vero

22

double SumPot(int N){ if (N==0) return 1; else return pow(2,N)+SumPot(N-1);}

Algoritmo ricorsivo per calcolare la somma delle potenze di 2 tra 0 e N

23

In fig. è mostrato

lo stack dei processi aperti

nel caso di N=5

Algoritmo ricorsivo:Fare la somma delle potenze di 2 tra 0 e N

16+ SumPot (4) SumPot =31

8+ SumPot (3)

4+ SumPot (2)

2+SumPot (1)

1+ SumPot(0) SumPot =1

SumPot =3

SumPot =7

SumPot =15

32+ SumPot (5) SumPot =63

Inizio del processo

Caso base

Risultato

24

In allegato è mostrato un codice che calcola:

La somma dei numeri interi tra 1 e NIl valore di 2N

La somma delle potenze di 2i con 0<=i<=N

Allegato: sommaRic

1111111

1111

1

11

11

11

11

ESERCIZI

Calcolare con una funzione ricorsiva le seguenti espressioni:

a)

b)