Ricorsione

Iterare è
umano, usare
la ricorsione
divino.
(Anonimo)

Introduzione
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.
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, …)

Principio di induzione
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 n2 + n + 41.
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.
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: sia P(n) un enunciato parametrizzato rispetto ad un numero naturale n.
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.

Definizioni ricorsive
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 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

La programmazione ricorsiva
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, …).

Prima funzione ricorsiva: fattoriale
unsigned long fatt (unsigned int n)
{if ( n == 0)
return 1;
else
return n*fatt (n-1);}

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.

Osservazioni
- 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.
- 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);
}

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

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

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

Lo “spirito” del metodo ricorsivo
- 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.

Numeri di Fibonacci (1170-1250, matematico italiano(PISA))
- 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;
}