Corso di Fondamenti di Informatica IIwebuser.unicas.it/.../dida/FI20910/Appunti/lezione5.pdf ·...

Corso di Fondamenti di Informatica II

a.a. 2009/2010Francesco Fontanella

La ricorsione

Francesco Fontanella, Corso di Fondamenti di Informatica II

a.a. 2009/2010 2

La ricorsione

■ Si dice che un oggetto (una struttura dati, una funzione matematica, un concetto…) è ricorsivo se è possibile darne una definizione in termini di (varianti di) sè stesso

■ Esempio: la funzione matematica fattoriale– n!=n*(n-1)! Se n≥1– 0!=1

■ Esempio: la definizione di sequenza– Una sequenza è la sequenza vuota oppure è un elemento seguito da una

sequenza:

– s ≡ x1 U s’– s’ ≡ x2 U s’’

– s’’ ≡ x3 U s’’’

.

.

– sn ≡<>


a.a. 2009/2010 3

La ricorsione

■ Esempio: una filastrocca per bambini …– C'era una volta un re seduto sul sofà che disse alla sua serva raccontami una

storia e la serva incominciò: C'era una volta un re...

■ Esempio: in natura…


a.a. 2009/2010 4

Il Principio dell'induzione

■ Il principio d'induzione è un enunciato sui numeri naturali che in matematica trova un ampio impiego nelle dimostrazioni:

■ In pratica: – si dimostra che vale P(1) (o P(0)), cioè che la proprietà P vale per 1(o 0).– si assume come ipotesi che l'asserto P(n) valga per un generico n e da tale

assunzione si dimostra che vale anche P(n + 1)


a.a. 2009/2010 5

Il Principio dell'induzione: un Esempio

■ Dimostriamo che vale l'asserto:

Vogliamo quindi dimostrare la seguente proprietà P

Base dell'induzione: l'asserto è vero per n=1:

Passo induttivo:

∀n∈ℕ 123n=n n12

P n=123n=n n12


a.a. 2009/2010 6

Il Principio dell'induzione: un Esempio

Passo induttivo:

Possiamo facilmente asserire che

Da ciò, inpochi passi è facile dmostrare l'asserto:

P n=n n12

⇒ P n1=n1n11

2

P n1=123nn1=P nn1

P n1=nn12

n1=n1n11

2


a.a. 2009/2010 7

La Ricorsione

■ In programmazione la ricorsione è una tecnica potente che: permette di suddividere un problema da risolvere in sottoproblemi simili a quello

originale

■ la potenza della ricorsione nasce dalla possibilità di definire un insieme infinito di oggetti con regola finita

■ …allo stesso modo, un insieme infinito di computazioni può essere descritto con un programma ricorsivo finito.

■ La ricorsione si applica ad algoritmi ricorsivi (i quali a loro volta sono spesso basati su strutture dati ricorsive)

■ Per tali algoritmi la tecnica ricorsiva permette di scrivere programmi eleganti e sintetici, sarà tuttavia opportuno verificarne di volta in volta l'efficienza rispetto ad altri tipi di soluzioni


a.a. 2009/2010 8

Il programma fattoriale

■ La versione ricorsiva del fattoriale è:int fatt(int x){

int f;if (x<=1) f=1;else f=x*fatt(x1);return f;

}

■ Mentre quella iterativa è:int fatt(const int x){ int f=1,i; for(i=1;i<=x;i++)

f=f*i; return f;}

passo BASE

Passo INDUTTIVO


a.a. 2009/2010 9

Lo schema degli algoritmi ricorsivi

■ Un algoritmo ricorsivo è sempre codificato per mezzo di un programma che richiama se stesso:

P (T1 x) {...if (p(x)) F;else C(S,P);R

}

int fatt(int x){int f;if (x<=1) f=1;else f=x*fatt(x1);return f;

}

Il predicato p(x) verifica il caso BASE


a.a. 2009/2010 10

Terminazione

■ La chiamata ricorsiva deve quindi essere subordinata ad una condizione che ad un certo istante risulti soddisfatta (il predicato p).

■ Il numero di chiamate necessarie viene detto profondità della ricorsione


a.a. 2009/2010 11

Algoritmi ricorsivi

■ Esistono diversi tipi di algoritmi ricorsivi:

– Si parla di mutua ricorsione quando nell'algoritmo una funzione ne richiama un'altra che a sua volta richiama la prima, altrimenti si parla di ricorsione diretta

– Si parla di ricorsione lineare quando vi è solo una chiamata ricorsiva all'interno della funzione, e di ricorsione non lineare nel caso in cui le chiamate ricorsive siano più di una.

– La distinzione più importante ai fini pratici si ha fra ricorsione di coda (tail recursion) e ricorsione non di coda. Si parla di ricorsione di coda quando la chiamata ricorsiva è l'ultima istruzione eseguita nella funzione. Questo tipo di algoritmo ricorsivo è possibile trasformarlo semplicemente in una versione iterativa, che di solito è più efficiente,


a.a. 2009/2010 12

Meccanismo interno di ricorsione

■ Un sottoprogramma ricorsivo è dunque un sottoprogramma che richiama direttamente o indirettamente se stesso

■ Non tutti i linguaggi realizzano il meccanismo della ricorsione. Quelli che lo realizzano possono utilizzare due tecniche:

– gestione LIFO di più copie della stessa funzione, ciascuna con il proprio insieme di variabili locali

– Gestione mediante record di attivazione; un’ unica copia del codice del sottoprogramma ma ad ogni chiamata è associato un record di attivazione (variabili locali e punto di ritorno). In questo caso diversi record di attivazione dello stesso sottoprogramma possono essere contemporaneamente presenti nello stack


a.a. 2009/2010

Schema ricorsivo

main........fatt(3)

fatt(2)

if (x<=1) f=1;else f=x*fatt(x-1);

return f;

fatt(1)


return f;126

Fase discendente

Fase ascendente

fatt(3)


return f;


a.a. 2009/2010

Dalla forma ricorsiva a quella iterativa

Un problema ricorsivo può sempre essere risolto in termini iterativi (il viceversa non è vero).Nel caso in cui la ricorsione è in coda, la trasformazione è molto semplice. Ad esempio:

Quando invece la ricorsione non è l'ultima istruzione della procedura si può optare per una soluzione che preveda l'utilizzo di uno stack di supporto che permette di salvare i valori delle chiamate ricorsive e tramite un ciclo while simulare ciò che fa lo stack di sistema.

P (T1 x) {...if p(x) F;else {S;P(x);}return

}

while !p(x)S;

F;


a.a. 2009/2010

Dalla forma ricorsiva a quella iterativa: il fattoriale

int fatt(const int x){ int f; if (x<=1) f=1; else f=x*fatt(x-1); return f;}

int fatt(const int x){ int f=1,i; for(i=1;i<=x;i++)

f=f*i; return f;}

Forma ricorsiva Forma iterativa


a.a. 2009/2010

Alcuni esempi

■ Esponenziale

■ Calcolo lunghezza di un stringa

■ Ricerca del minimo.

■ Ricerca di un valore

■ Stringa palindrome

■ Inversione di un stringa


a.a. 2009/2010

Esponenziale

float exp( float x, int n)

{ if (n == 1)

return x;else return x*exp(n1);

}

NOTAQuesta versione tiene conto solo di esponenti positivi. Provare a scrivere la stessa funzione (ricorsiva) tenendo conto anche del caso n < 0

ricorsione in coda


a.a. 2009/2010

Calcolo Lunghezza di una Stringa

void exp( float x, int n)

{ if (n == 1)

return x;else return x*exp(n1);

}

ricorsione in coda

void strlen( char *str)

{ if (str[0] == '\0')

return 0;else return 1 + strlen(&str[1]);

}

Posso anche scrivere:*str == '\0'


a.a. 2009/2010

Funzione di Ricerca del Minimo ricorsiva

int ric_min( int n, int v[])

{ int m; if (n==1)

return v[0];

m = ric_min(n1, &v[1]); if (m < v[0]) return m; else return v[0];

}

NOTAQuesto è un caso di ricorsione non in coda


a.a. 2009/2010

Funzione di Ricerca di valore ricorsiva

bool check_val( int n, int v[], int val) { if (v[0] == val) return true; else if (n > 1) return check_val(n1, v+1, val); }

Uso dell'aritmetica dei puntatori


a.a. 2009/2010

Palindrome

■ Stringa palindrome:– uguale se letta nei due versi: anna, radar, asorrosa, abbbcbbba

■ Una stringa è palindrome se: – ha un solo carattere, oppure– è composta da un primo ed ultimo carattere uguali che racchiudono una

stringa ancora palindrome


a.a. 2009/2010

Palindrome

bool palindrome(char str[], int first, int last) { if (str[last] == str[first]){ if ((last – first) <= 1) return true; else return palindrome(str, first+1, last1); } else return false; }

NOTAProvare a scrivere la versione iterativa

Corso di Fondamenti di Informatica IIwebuser.unicas.it/.../dida/FI20910/Appunti/lezione5.pdf ·...

Documents

Transcript of Corso di Fondamenti di Informatica IIwebuser.unicas.it/.../dida/FI20910/Appunti/lezione5.pdf ·...