OCaml
Rekursion för svans
Sök…
Introduktion
Funktionella språk som OCaml förlitar sig starkt på rekursiva funktioner . Sådana funktioner kan emellertid leda till minne över förbrukning eller, vid hantering av stora datamängder, att stapla överflöden .
Rekursion för svans är en viktig källa till optimering i sådana fall. Det tillåter ett program att släppa samtalskontext när det rekursiva samtalet är det sista av funktionen .
Sumfunktion
Nedan visas en icke-svansrekursiv funktion för att beräkna summan av en lista med heltal.
let rec sum = function
| [] -> 0
| h::t -> h + (sum t)
Den sista åtgärden som funktionen utför är tillägget. Funktionen är alltså inte svårrekursiv.
Nedan visas en svansrekursiv version av samma funktion.
let sum l =
let rec aux acc = function
| [] -> acc
| h::t -> aux (acc+h) t
in
aux 0 l
Här är aux funktionen svansrekursiv: den sista operationen som den utför är att ringa sig själv. Som en konsekvens kan den senare versionen av sum användas med listor av valfri längd.