[Informatik-Seminar WS2004/05] [Inhalt] [Zurück] [Weiter]
Bei der Verwendung von Rekursion ist darauf zu achten, dass diese end-rekursiv sind. Dies vermeidet das interne Verwalten von Zwischenergebnissen.
Diese Funktion berechnet die Fakultät einer Zahl x. Das Ergebnis der Funktion ist Teilrekursiv, da der Parameter x mit dem Ergebnis des nächsten Rekursionsschritt multipliziert wird. Für jeden Rekursionsschritt muss also der Wert des Parameters x im Stack gehalten werden.
(define fak
(lambda (x)
(if (= x 0)
1
(* x (fak (- x 1))))))
Dies lässt sich ändern, indem man das bisherige Ergebnis als Parameter mitführt. Dadurch wird nur durch den aktuellen Rekursionsschritt Speicherplatz belegt.
(define fak-iter
(lambda (x a)
(if (= x 0)
a
(fak-iter (- x 1) (* x a)))))
Zum besseren Aufruf erstellt man dann noch eine Funktion, die die Initialisierung der endrekursiven Funktion vornimmt.
(define fak
(lambda (x)
(fak-iter x 1)))
Die map Funktion ermöglicht das Anwendern einer Funktion auf Listen. Dabei wird die angegebene Funktion nacheinander auf alle Elemente der angegebenen Liste angewendet. Die Funktion erhält jeweils ein Element als Argument. Als Ergebnis erhält man eine Liste mit allen einzelnen Ergebnissen. Es ist auch möglich eine Funktion, die mehrere Argumente fordert zu verwenden. Dazu muss man dann mehrere Listen übergeben.
Hier wird die Funktion abs auf die Elemente -1, 2, -3, -4 und 5 angwendet.
(map abs '(-1 2 -3 -4 5)) => (1 2 3 4 5)
Die Addition dient als Beispiel für eine Funktion mit zwei Argumenten.
(map + '(1 2 3) '(4 5 6) ) => (5 7 9)
[Informatik-Seminar WS2004/05] [Inhalt] [Zurück] [Weiter] [Seitenanfang]