Algoritmo ricorsivo
Da Wikipedia, l'enciclopedia libera.
Viene detto algoritmo ricorsivo un algoritmo espresso in termini di se stesso.
Questo tipo di algoritmo risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di input variabili. L'algoritmo richiama se stesso generando un ciclo di chiamate che ha termine al verificarsi di una condizione particolare che chiameremo caso di base, coincidente, in genere, con il presentarsi di particolari valori di input. La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, sarà tuttavia opportuno verificarne di volta in volta l'efficienza rispetto ad altri tipi di soluzioni, come per esempio cicli elementari. In alcuni casi la ricorsione è altrettanto efficiente di un ciclo iterativo: linguaggi dei paradigmi funzionali o logici tipicamente non hanno il concetto di ciclo ed usano la ricorsione ottimizzando automaticamente (Tail call optimization).
Indice |
[modifica] Il punto di partenza: il fattoriale
Per capire il concetto useremo un esempio di tipo matematico, il calcolo del fattoriale di un numero n. Un altro semplice esempio potrebbe essere stato quello della Successione di Fibonacci.
Chiameremo fattoriale di n e scrivermo n!, il prodotto dei primi n numeri naturali, ottenuto come segue:
0! = 1;
n! = 1 * 2 * 3 * ...... * n-1 * n; per n > 0.
Modificando leggermente la definizione, ci si accorge di come sia possibile darne una versione ricorsiva. Sia a tal proposito:
n! = (1 * 2 * 3 * ...... * n-1) * n;
si ottiene,
n! = (n-1)! * n;
da cui, iterando,
n! = (n-2)! * n-1 * n,
continuando ad iterare la definizione, arriveremo ai casi di base per i quali il risultato cercato è noto,
0! = 1! = 1.
Siamo adesso in grado di dare un algoritmo ricorsivo che chiameremo FATT, per il calcolo del fattoriale. Si osservi che la notazione utilizzata distingue tra il simbolo x == y, per indicare uguaglianza tra i due valori ed il simbolo x = y, per indicare che alla variabile x sarà assegnato il valore di y, così come per il Linguaggio C:
FATT (n)
if n == 0 or n == 1
return 1
else
return n * FATT (n-1)
Quando l'algoritmo viene eseguito la prima volta, il valore di n viene confrontato con 0 e con 1, nel caso in cui il valore sia diverso, la procedura viene chiamata ricorsivamente su valori più piccoli sino a quando n non risulta uguale ad 1, nel qual caso il risultato è noto e può essere restituito dalla funzione attuale a quella che l'aveva in precedenza chiamata. I risultati restituiti da ognuna delle procedure ricorsive vengono di volta in volta moltiplicati. Il penultimo valore restituito sarà proprio uguale ad (n-1)!, quest'ultimo verrà moltiplicato per n e l'algoritmo potrà restituire il risultato cercato.
A scopo esplicativo e didattico, viene fornito di seguito un algoritmo per il calcolo del fattoriale che sfrutta un approccio di tipo iterativo:
FATTiterativo (n)
fatt = 1
i = 2
while i <= n
fatt = fatt * i
i + 1
return fatt
[modifica] Tipi di ricorsione
Esistono vari tipi di ricorsione. 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.
Altra distinzione è quella fra ricorsione lineare, che si ha quando vi è solo una chiamata ricorsiva all'interno della funzione, e 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, in quanto non occorre mantenere lo stato della funzione una volta calcolata come è stato fatto nell'esempio precedente. Se l'algoritmo non è ricorsivo di coda, per trasformarlo in una versione iterativa occorre utilizzare un meccanismo di mantenimento dello stato analogo a quello che è utilizzato implicitamente nelle chiamate di funzione.
[modifica] Requisiti di un algoritmo ricorsivo
Non tutti gli algoritmi possono essere espressi in forma ricorsiva. Esistono in generale tre requisiti fondamentali affinché un algoritmo sia effettivamente esprimibile in forma ricorsiva.
- Il primo è, banalmente, la possibilità di formulare l'algoritmo in funzione di sé stesso.
- Il secondo è che non si verifichi mai un ciclo infinito: è necessario che in qualche modo l'applicazione del processo termini, ovvero deve esistere una condizione di terminazione, ovvero almeno una istanza del processo che non richiede di essere scomposta in ulteriori istanze più semplici. Nell'algoritmo del fattoriale è rappresentata da 1! o da 0!.
Inoltre non deve esistere un valore di ingresso che renda impossibile la terminazione dell'esecuzione. Nell'esempio del fattoriale, si evince chiaramente che se viene inserito un numero negativo, il programma chiamerà infinite istanze della funzione fatt(), perché non arriverà mai alla condizione di terminazione n==0||n==1. Ciò si risolve facilmente applicando un controllo o utilizzando un tipo (come unsigned) che non ammetta valori negativi. I casi di overflow non rientrano in questo requisito in quanto generano direttamente un errore di run-time (cosa che, in pratica, avviene inserendo un negativo).
- Il terzo requisito è la convergenza insiemistica.
Non tutti gli insiemi di definizione degli algoritmi, in funzione della relativa formulazione, permettono la ricorsione. Dimostriamolo con un esempio: Supponiamo di formulare una funzione A(x) come segue:
Risulta abbastanza evidente che inserendo un numero dispari in ingresso la funzione non andrà mai a 1. Nella pratica si verifica un ciclo infinito che terminerà con un errore di run-time dovuto all'esaurimento della memoria per eccessivo overhead. Tuttavia ciò deve spingere il progettista software a capire in anticipo quando un algoritmo può essere ricorsivo o meno.
[modifica] Vantaggi e svantaggi
La ricorsione ha un vantaggio fondamentale: permette di scrivere poche linee di codice per risolvere un problema anche molto complesso. Tuttavia essa ha anche un enorme svantaggio: le prestazioni. Due sono le cause:
- In ogni caso la ricorsione genera una quantità enorme di overhead, invadendo gli stack di memoria per un numero di istanze pari alle chiamate. Funzioni che occupano una grossa quantità di spazio in memoria, pur potendo essere implementate ricorsivamente, potrebbero dare problemi a tempo di esecuzione. Inoltre la ricorsione impegna comunque il processore in maniera maggiore per popolare e distruggere gli stack
- Su alcuni processori, inoltre, è presente un Link Register utilizzato direttamente dalle chiamate assembly di istruzioni simili alla JSR del Motorola 68000. Tale Link Register permette al processore di saltare dall'exit-point di una subroutine alla sua chiamante. Questo fenomeno accade soprattutto nei palmari, ed è causa di errori di compilazione o di run-time. Nei compilatori più avanzati, il tutto si risolve con un calo considerevole delle prestazioni dovuto all'utilizzo di istruzioni assembly alternative.
Pertanto, se le prestazioni sono obiettivo principale del programma e non si dispone di sufficiente memoria, si consiglia di non utilizzare la ricorsione.
[modifica] Applicazioni principali
La ricorsione può essere quasi sempre applicata alla gestione di dati in formato XML. Grazie alle API fornite con tutti i linguaggi di programmazione moderni, basate sul polimorfismo, è possibile formulare praticamente tutti gli algoritmi di lettura/creazione XML in maniera ricorsiva. Ancora, algoritmi di ordinamento efficienti come Quicksort e Merge sort o algoritmi di ricerca come la ricerca binaria possono essere formulati in maniera ricorsiva, anche con tipi di dati come le liste a puntatori.
[modifica] Eliminazione delle ricorsione
Sono stati fatti degli studi approfonditi su come ottimizzare il codice di alcune routine dove il carico della memoria di allocazione delle funzioni è troppo elevato. Si effettuano degli studi sulla natura della funzione e si ricava l'eliminazione della ricorsione per un'ottimizzazione della memoria.
[modifica] Ricorsione in coda
void F(x)
{
if P(x) then {D;}
else
{
E; y=g(x); F(y);
}
}
Si noti come la chiamata ricorsiva sia l’ultima istruzione della funzione. Si può quindi facilmente eliminarla sostituendola con un costrutto iterativo
void F_it(x)
{
while (P(x)==0) then
{E; x=g(x);}
{D;}
}
Si consideri la procedura di ricerca binaria (ricorsiva) in un vettore ordinato
int binsearch(int a[], int sx, int dx, int el)
{
int x;
if (dx < sx) return -1;
x = (dx + sx)/2;
if (el < a[x]) return binsearch(a,sx,x-1,el);
else if (el == a[x]) return x;
else return binsearch(a,x+1,dx,el);
}
Osserviamo che le chiamate ricorsive sono eseguite come ultime istruzioni della funzione. Sviluppiamo una versione iterativa per la ricerca binaria
int binsearch_it(int a[], int dim, int el)
{ int sx, dx, x;
sx = 0; dx = dim - 1;
while (dx >= sx)
{ x = (dx + sx)/2;
if (el == a[x]) return x;
if (el < a[x]) dx = x - 1;
else sx = x + 1;
}
return -1;
}
[modifica] Ricorsione non in coda
Quando invece la ricorsione non è l'ultima istruzione della procedura (ricorsione in coda) 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 in modo del tutto banale ciò che fa lo stack di sistema.
[modifica] Curiosità
L' algoritmo ricorsivo è protagonista del libro Crypto dello scrittore Dan Brown.
