Esplorazione della ricorsione: concetti, esempi e applicazioni

Iterare è

umano, usare

la ricorsione

divino.

(Anonimo)

Problema e soluzione

Problema: Si consideri il problema di dover versare la somma di 16,51€ con il minor numero possibile di pezzi, tra banconote e monete.

Soluzione: Il problema può essere suddiviso in due sottoproblemi: versare 10,00€ e versare 6,51€ Il primo sottoproblema può essere subito risolto con una banconota da 10,00€, mentre il secondo sottoproblema è molto simile al problema di partenza, ad eccezione del fatto che la somma da versare è più piccola.

Concetto di ricorsione

La ricorsività è semplicemente il processo per risolvere un problema riducendolo in sottoproblemi che sono:

Identici in struttura al problema originale

Un po’ più semplice da risolvere.

Una funzione è detta ricorsiva quando direttamente (ricorsione semplice) o indirettamente (ricorsione mutua) chiama se stessa.

Ricorsione dal latino re - currere (ricorrere, fare ripetutamente la stessa azione).

Il concetto di ricorsione viene usato nel contesto di:

- Algoritmi

- Strutture dati (liste, alberi, …)

Il termine ricorsione indica la possibilità in una definizione di far ricorso alla definizione stessa (definizione ricorsiva).

Definizione ricorsiva (o per induzione) dei numeri naturali N:

- 0 è un numero naturale

- se n è un numero naturale, allora n+1 è un numero naturale.

Consideriamo un enunciato o proposizione che contenga come parametro un numero

naturale n e la indichiamo genericamente con P(n).

- Ci chiediamo se P(n) sia vera o falsa.

- Eulero (1707-1783,matematico e fisico svizzero) ha proposto lo studio dei valori del trinomio E’ ingenuo ritenere che una certa P(n) sia vera per tutti gli n se è vera solo per alcuni.

- Data una P(n) basta un contro-esempio per concludere che è falsa.

- Per dimostrare che P(n) è vera non bastano 10, 100, 1000… verifiche.

Principio di induzione

Il principio di induzione (matematica) è una tecnica per dimostrare che una famiglia di proposizioni P(n) è vera per ogni n appartenente a N.

Principio di induzione: Dalla verità dei seguenti due enunciati:

- Base di induzione: P(0) è vero;

- Passo induttivo: detto n un generico numero naturale, se P(n) è vero (ipotesi di induzione) allora anche P(n+1) è vero;

si deduce che P(n) è vero per ogni n appartenente a N.

Definizione ricorsiva del fattoriale

Definizione ricorsiva (o per induzione) di fattoriale di un numero naturale n.

- 0! = 1 (chiusura della ricorsione/base di induzione)

- n! = n (n - 1)! (passo ricorsivo/passo induttivo)
Definizione iterativa di fattoriale: il fattoriale di n è il prodotto dei numeri naturali compresi tra 1 ed n.

Giustificazione della posizione 0!=1

n! = 1 * 2 * 3 * … * n per n >=1

n+1)! = (n+1)n!

Per n = 0, sostituendo si ha:

1! = 1*0! => 0! = 1/1 = 1

Definizione ricorsiva della potenza

Definizione ricorsiva della potenza di un numero a ≠ 0.

a^n = 1 se n = 0

a^n = a*an-1 se n > 0

Giustificazione che a 0 = 1

a^n = a * a * … * a (n fattori)

a^n+1 = a * an

per n = 1, a^2 = a * a^1 => a^1 = a*a/a = a

per n = 0, a^1 = a * a^0 => a^0 = a/a = 1

Una funzione è detta ricorsiva quando direttamente (ricorsione semplice) o indirettamente (ricorsione mutua) chiama se stessa.

- Ricorsione dal latino re-currere (ricorrere, fare

ripetutamente la stessa azione).

- Il concetto di ricorsione viene usato nel contesto di:

1) Algoritmi

2) Strutture dati (liste, alberi, …).

unsigned long fatt (unsigned int n)

{if ( n == 0)

return 1;

else

return n*fatt (n-1);}

Esempio di calcolo del fattoriale

Calcoliamo fatt(3), indicando passo passo le operazioni che vengono eseguite dal

sistema e che rimangono nascoste al programmatore.

Fatt(3) = 3 * fatt(2) = 3*2*fatt(1) = 3*2*1 *fatt(0)= 3*2*1*1 = 6

- Nel “ramo allora” troviamo la condizione di chiusura delle chiamate successive.

- Nel “ramo altrimenti” troviamo la definizione vera e propria che ha la forma di una nuova chiamata di se stessa fatt(n-1).

- L’algoritmo decrementa il valore di n fino a 0, conservando in un apposito spazio di memoria, in pila uno sull’altro, i valori successivi del parametro n fino al valore 0. In questa fase di chiamate ricorsive non viene eseguito alcun calcolo; non appena n = 0 vengono eseguiti i calcoli a ritroso secondo i valori di n prelevati dalla pila, in ordine inverso rispetto a quello dell’immissione.

- E’ importante notare come i valori di n vengono modificati ad ogni chiamata, mentre la pila (STACK) consente di non perdere i valori precedenti.

- Nei linguaggi che consentono la ricorsione questa gestione è un fatto interno al sistema della quale il programmatore non si deve curare.

- La traccia indicata consente una verifica sulla correttezza delle funzioni/procedure ricorsive adottate ed è un aiuto al programmatore all’atto della verifica di un pgm.

La convenienza nell’uso dello STACK è che le procedure terminano in ordine inverso a quello di attivazione e che quindi i record stessi seguono la medesima

sorte.

Calcolo del MCD

- Scrivere una funzione C che calcoli il MCD fra due interi a e b con il metodo ricorsivo della sottrazione.

MCD(a,b) = a se a = b

MCD(a,b)=MCD(a-b,b) se a > b

MCD(a,b)=MCD(b-a,a) se a

int mcd (int a, int b)

{

if(a == b)

return a;

else if (a > b)

return mcd(a-b,b);

else

return mcd(b-a,a);

}

Calcolare il MCD fra 4 interi, scrivere una sola istruzione.

int risult=mcd(mcd(a,b),mcd(c,d));

Regole per algoritmi ricorsivi

- E’ buona norma ricordare le regole applicate nella formulazione degli alg. ricorsivi, in quanto condizioni necessarie non sufficienti per ottenere la correttezza, precisamente:

1. Deve essere sempre presente la condizione di chiusura della ricorsione.

2. Ogni successiva chiamata deve riferirsi a valori minori di quello di partenza o ad un sottoinsieme dell’insieme originale di elementi.

- Esiste un CASO BASE, rappresentante un sotto-problema facilmente risolubile.

- Per es.,nel caso del fattoriale, se n=0 so calcolare il fattoriale di n,vale 1.

- Negli altri casi ci si deve ricondurre al caso base.

- La potenza di una definizione ricorsiva è legata alla possibilità di definire un insieme di oggetti infinito mediante una descrizione finita.

- Numeri di Fibonacci

f0 = 1, f1 = 1

fn = fn-1 + fn-2 per n >= 2

int fibonacci (int n)

{

int ris;

if(n == 0)

ris=1;

else if(n == 1)

ris = 1;

else

ris = fibonacci(n-1) + fibonacci(n-2);

return ris;

}