OCaml
Recursion de cola
Buscar..
Introducción
Los lenguajes funcionales como OCaml dependen en gran medida de las funciones recursivas . Sin embargo, tales funciones pueden llevar a la memoria a un consumo excesivo o, cuando se manejan grandes conjuntos de datos, a apilar desbordamientos .
La recursión de la cola es una fuente importante de optimización en tales casos. Permite que un programa descarte el contexto de la persona que llama cuando la llamada recursiva es la última de la función .
Función de suma
A continuación se muestra una función no recursiva de cola para calcular la suma de una lista de enteros.
let rec sum = function
| [] -> 0
| h::t -> h + (sum t)
La última operación que realiza la función es la suma. Por lo tanto, la función no es recursiva de cola.
A continuación se muestra una versión recursiva de la cola de la misma función.
let sum l =
let rec aux acc = function
| [] -> acc
| h::t -> aux (acc+h) t
in
aux 0 l
Aquí, la función aux es recursiva de cola: la última operación que realiza se llama a sí misma. Como consecuencia, la última versión de sum puede usarse con listas de cualquier longitud.