OCaml
Ricorsione di coda
Ricerca…
introduzione
I linguaggi funzionali come OCaml si basano molto sulle funzioni ricorsive . Tuttavia, tali funzioni possono comportare un consumo eccessivo della memoria o, durante la gestione di set di dati di grandi dimensioni, lo stack overflow .
La ricorsione della coda è una fonte importante di ottimizzazione in questi casi. Consente a un programma di eliminare il contesto del chiamante quando la chiamata ricorsiva è l'ultima della funzione .
Funzione di somma
Di seguito è riportata una funzione non ricorsiva alla coda per calcolare la somma di un elenco di numeri interi.
let rec sum = function
| [] -> 0
| h::t -> h + (sum t)
L'ultima operazione eseguita dalla funzione è l'aggiunta. Quindi, la funzione non è coda-ricorsiva.
Di seguito è riportata una versione ricorsiva in coda della stessa funzione.
let sum l =
let rec aux acc = function
| [] -> acc
| h::t -> aux (acc+h) t
in
aux 0 l
Qui, la funzione aux è ricorsiva in coda: l'ultima operazione che esegue si chiama da sola. Di conseguenza, l'ultima versione della sum può essere utilizzata con elenchi di qualsiasi lunghezza.