[:it]Come funziona la ricorsione[:]

[:it]

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.

[:]

Questa voce è stata pubblicata in Senza categoria. Contrassegna il permalink.

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *