OCaml
Schwanzrekursion
Suche…
Einführung
Funktionssprachen wie OCaml sind stark von rekursiven Funktionen abhängig . Solche Funktionen können jedoch zu Speicherüberlastung oder bei der Verarbeitung großer Datenmengen zu Stapelüberläufen führen .
Die Rekursion des Schwanzes ist in solchen Fällen eine wichtige Optimierungsquelle. Damit kann ein Programm den Aufruferkontext löschen, wenn der rekursive Aufruf der letzte der Funktion ist .
Summenfunktion
Nachfolgend finden Sie eine nicht rekursive Funktion zum Berechnen der Summe einer Liste von Ganzzahlen.
let rec sum = function
| [] -> 0
| h::t -> h + (sum t)
Die letzte von der Funktion ausgeführte Operation ist die Addition. Daher ist die Funktion nicht rekursiv.
Nachfolgend finden Sie eine rekursive Version der gleichen Funktion.
let sum l =
let rec aux acc = function
| [] -> acc
| h::t -> aux (acc+h) t
in
aux 0 l
Die aux Funktion ist hier rekursiv: Die letzte von ihr ausgeführte Operation ruft sich selbst auf. Folglich kann die letztere Version der sum mit Listen beliebiger Länge verwendet werden.