OCaml
Staart recursie
Zoeken…
Invoering
Functionele talen zoals OCaml zijn sterk afhankelijk van recursieve functies . Dergelijke functies kunnen echter leiden tot geheugenoverconsumptie of, bij het verwerken van grote gegevenssets, tot overloop .
Staartrecursie is in dergelijke gevallen een belangrijke bron van optimalisatie. Hiermee kan een programma de context van de beller verwijderen wanneer de recursieve oproep de laatste functie is .
Som functie
Hieronder staat een niet-staartrecursieve functie om de som van een lijst met gehele getallen te berekenen.
let rec sum = function
| [] -> 0
| h::t -> h + (sum t)
De laatste bewerking die de functie uitvoert, is de toevoeging. De functie is dus niet staartrecursief.
Hieronder staat een staartrecursieve versie van dezelfde functie.
let sum l =
let rec aux acc = function
| [] -> acc
| h::t -> aux (acc+h) t
in
aux 0 l
Hier is de aux functie staartrecursief: de laatste bewerking die hij uitvoert, roept zichzelf op. Bijgevolg kan de laatste versie van sum worden gebruikt met lijsten van elke lengte.