Stack o pila
La funzione che implementa il calcolo del fattoriale di un numero è un esempio di calcolo ricorsivo.
funzione fattoriale(intero n)
se n=0
ritorna il valore 1
altrimenti
n=n*fattoriale(n)
In pratica l’elaboratore mette in parcheggio il valore della variabile n finchè essa non ritorna il valore 1. La memoria dell’elaboratore crea delle aree di memoria che assumono il valore precedente come una pila.
Prima riempie la pila e poi la svuota terminando. Ossia nel primo gradino mette il valore più elevato poi, man mano che aumenta inserisce il valore meno elevato.
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.
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.