Algoritmo ricorsivo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
←Pagina sostituita con 'Vedi: Algoritmo ricorsivo{{portale|informatica|matematica}} Categoria:Algoritmi Categoria:Ricorsione' |
m Annullate le modifiche di 195.169.202.118 (discussione), riportata alla versione precedente di 95.246.72.107 |
||
Riga 1:
{{nota disambigua|la ricorsività in ambito linguistico|Ricorsività (linguistica)|Ricorsività}}
{{F|programmazione|febbraio 2013}}
[[File:SierpinskiTriangle.svg|thumb|[[Triangolo di Sierpiński]]]]
In [[informatica]] viene detto '''algoritmo ricorsivo''' un [[algoritmo]] espresso in termini di se 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.
Tale tecnica risulta particolarmente utile per eseguire dei compiti ripetitivi su di un set di variabili in [[input]]. L'algoritmo richiama se 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ù efficienti. Questo è dovuto al fatto che comunemente la ricorsione viene implementata utilizzando le [[funzione (informatica)|funzioni]], e che l'invocazione di una funzione ha un costo rilevante, e questo rende più efficienti gli algoritmi [[iterazione|iterativi]].
In alcuni casi la ricorsione è altrettanto efficiente di un [[iterazione|ciclo iterativo]]: linguaggi dei [[Paradigma di programmazione|paradigmi]] [[Programmazione funzionale|funzionali]] o [[Programmazione logica|logici]] tipicamente non hanno il concetto di ciclo ed usano la ricorsione ottimizzando automaticamente ([[Tail call optimization]]).
== 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 scriveremo '''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 (linguaggio)|C]]:
'''int FATT (int n)'''
{
if (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 [[algoritmo iterativo|iterativo]]:
'''int FATTiterativo (int n)'''
{
int fatt = 1;
while (1 <= n)
{
fatt = fatt * n;
n --;
}
return fatt;
}
== 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.
== Espressività della ricorsione ==
Ricorsione ed iterazione hanno la stessa espressività: la ricorsione può essere rimpiazzata dall'iterazione tramite l'utilizzo di uno stack esplicito, mentre l'iterazione può essere rimpiazzata con la ricorsione di coda. Quale approccio sia il migliore dipende dal problema da risolvere e dal linguaggio utilizzato. Nel caso dei linguaggi imperativi si preferisce l'uso dell'iterazione, particolarmente nel caso di ricorsione lineare, poiché evita l'[[overhead]] delle chiamate di funzione e della gestione dello [[stack (informatica)|stack]], mentre nei linguaggi funzionali, al contrario si preferisce l'uso della ricorsione, in cui la versione di coda è sovente ottimizzata con prestazioni paragonabili all'iterazione.
== 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 (informatica)|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 [[run-time|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.
== Applicazioni principali ==
* algoritmi su [[albero (informatica)|alberi]]
* valutazione di funzioni matematiche
* gestione di aggregati eterogenei di dati, in combinazione con il [[Polimorfismo (informatica)|polimorfismo]]
* gestione di dati in formato [[XML]]. Grazie alle [[Application programming interface|API]] fornite con tutti i linguaggi di programmazione moderni, è possibile formulare praticamente tutti gli algoritmi di lettura/creazione XML in maniera ricorsiva.
* [[algoritmo di ordinamento|algoritmi di ordinamento]] efficienti come [[Quicksort]] e [[Merge sort]] o [[algoritmo di ricerca|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]].
== Eliminazione della ricorsione ==
Sono stati fatti degli studi approfonditi su come [[Ottimizzazione (informatica)|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.
=== Ricorsione in coda ===
La ricorsione in coda (''tail recursion'') si verifica quando, in una procedura e/o funzione ricorsiva (che richiama se 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 come si possa ottimizzare questa condizione sostituendo una funzione ricorsiva con una iterativa, che comporti minor complessità spaziale. Il passaggio da funzione ricorsiva a funzione 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 [[array|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;
}
=== Ricorsione non in coda ===
Quando invece la ricorsione non è l'ultima istruzione della procedura (ricorsione non 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.
== 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]].
== Voci correlate ==
* [[Funzione ricorsiva]]
* [[Funzione ricorsiva primitiva]]
* [[Master theorem]]
* [[Tesi di Church-Turing]]
* [[Effetto Droste]]
{{portale|informatica|matematica}}
[[Categoria:Algoritmi]]
| |||