La ricorsione

Corso di Fondamenti di Informatica

La ricorsione

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 ≡ x₁ U s’

s’ ≡ x₂ U s’’

s’’ ≡ x₃ U s’’’

. . – sⁿ ≡<>

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…

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)

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∈ℕ 1 2 3 . . 1

2

1 2 3 . . 1

2

Il Principio dell'induzione: un Esempio

Passo induttivo:

Possiamo facilmente asserire che

Da ciò, in pochi passi, è facile dimostrare l'asserto:

1 ⇒

2 1 1 1 1

2

1 1 2 3 . . 1 1

1 1

2 + 1 ^{1 1 1}

2

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

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

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

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

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 ricorsionelineare 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,

Meccanismo interno di ricorsione

■ Un sottoprogramma ricorsivo è dunque

direttamente o indirettamente se stesso un sottoprogramma che richiama

■ Non tutti i linguaggi realizzano il meccanismo

realizzano possono utilizzare due tecniche: della ricorsione. Quelli che lo – 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

Schema ricorsivo

m ain ...

...

..fatt(3)

fat t (2) if (x< = 1)

f= 1;

else

f= x* fat t (x-1);

ret urn f;

fat t (1) if (x< = 1)

f= 1;

else

f= x* fat t(x-1) ; ret urn f;

2 1 6

Fase ascendente Fase discenden te

fat t(3) if (x< = 1)

f= 1;

else

f= x* fat t (x-1) ;

ret urn f;

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:

while !p(x) S;

F

;

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 }

Dalla forma ricorsiva a quella iterativa: il fattoriale

i n t f a t t ( c o n s t i n t f ;

i f ( x < = 1 ) f = 1 ;

e l s e f = x * f a t t ( x - 1 ) ; r e t u r n f ;

}

i n t x ) { i n t f a t t ( c o n s t i n t x ) { i nt f =1, i ;

f or ( i =1; i < =x ; i ++) f = f * i ;

r e t u r n f ; }

Forma ricorsiva Forma iterativa

Alcuni esempi

■ Esponenziale

■ Calcolo lunghezza di un stringa

■ Ricerca del minimo.

■ Ricerca di un valore

■ Stringa palindrome

■ Inversione di un stringa

Esponenziale

float exp( float x, int n) {

if (n == 1) return x;

else return x*exp(n1);

}

ricorsione in coda

NOTA

Questa versione tiene conto solo di esponenti positivi. Provare a scrivere la

stessa funzione (ricorsiva) tenendo conto anche del caso n < 0

Calcolo Lunghezza di una Stringa

ricorsione in coda void strlen( char *str)

{

if (str[0] == '\0') return 0;

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

}

Posso anche scrivere:

*str == '\0'

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];

Funzione di Ricerca di valore ricorsiva

bool check_val( int n, int v[], int {

if (v[0] == val) return true;

else

if (n > 1)

val)

return check_val(n1, v+1, val);

}

Uso dell'aritmetica dei puntatori

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

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, } else return false;

last1);

}

NOTAProvare a scrivere la versione iterativa