Algoritmo ricorsivo
Da Wikipedia, l'enciclopedia libera.
Viene detto algoritmo ricorsivo un algoritmo espresso in termini di sé stesso, ovvero in cui l'esecuzione dell'algoritmo su un insieme di dati comporta la semplificazione o suddivisione dell'insieme di dati e l'applicazione dello stesso algoritmo agli insiemi di dati semplificati.
Questo tipo di algoritmo risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di input variabili. L'algoritmo richiama sé stesso generando una sequenza di chiamate che ha termine al verificarsi di una condizione particolare che viene chiamata condizione di terminazione, che in genere si ha con particolari valori di input.
La tecnica ricorsiva permette di scrivere algoritmi eleganti e sintetici per molti tipi di problemi comuni, anche se non sempre le soluzioni ricorsive sono le più efficenti. Questo è dovuto al fatto che comunemente la ricorsione viene implementata utilizzando le funzioni, e che l'invocazione di una funzione ha un costo rilevante, e questo rende più efficenti gli algoritmi iterativi.
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] Un esempio: 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.
Rielaborando 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 alle condizioni di terminazione, per cui 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
while (1 <= n)
fatt = fatt * n
n - 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. La regola che descrive tale possibilità è solitamente chiamata passo.
- 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, detta anche base, 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.
Infatti la ricorsione genera una quantità enorme di overhead, occupando lo stack per un numero di istanze pari alle chiamate della funzione che è necessario effettuare per risolvere il problema. 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
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
- Algoritmi su alberi
- valutazione di funzioni matematiche
- gestione di aggregati eterogenei di dati, in combinazione con il polimorfismo
- gestione di dati in formato XML. Grazie alle API fornite con tutti i linguaggi di programmazione moderni, è possibile formulare praticamente tutti gli algoritmi di lettura/creazione XML in maniera ricorsiva.
- 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.
- stesura di algoritmi che lavorano con la tecnica di backtracking.
- descrizione di curve frattali.
[modifica] Eliminazione della 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
La ricorsione in coda (tail recursion) si verifica quando in una procedura e/o funzione ricorsiva (che richiama sé stessa) la chiamata ricorsiva viene operata come ultimo passo. Ciò implica che al ritorno dalla chiamata ricorsiva la funzione non produce alcun altro passo. Srotolando la ricorsione si intuisce che si può ottimizzare questa condizioni sostituendo una funzione ricorsiva con una iterativa, che comporti minor complessità spaziale. Il passaggio da funzione ricorsiva a fuzione iterativa può essere operato semplicemente riproducendo per passi successivi l'intero corpo, appunto, della funzione.
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.
La soluzione del gioco d'ingegno noto con il nome Torre di Hanoi è facilmente descrivibile tramite un algoritmo ricorsivo.
La ricorsione può essere intesa anche come una versione costruttiva del principio d'induzione, dove il termine "costruttiva" indica la capacità di costruire la soluzione di un problema.
