Endrekursion (Haskell)
Aus Infostudium Wiki
Eine Endrekursion ist eine lineare Rekursion.
Zusätzlich muss gelten:
Alle rekursiven Aufrufe berechnen den Rückgabewert ohne Nachverarbeitung.
Eine Funktion ist endrekursiv, wenn kein rekursiver Aufruf in einem geschachtelten Ausdruck steht.
- D.h. darüber nur if, case, Wächter (engl. guards) oder Fallunterscheidungen.
- Entspricht while in imperativen Sprachen.
- Wird als Schleife implementiert.
Inhaltsverzeichnis |
Allgemein
Betrachte die folgende Summenfunktion:
-- ------ nicht optimale Lösung ---------- summe 0 = 0 summe n = n + summe (n-1) -- ---------------------------------------
Eine (teilweise verkürzte) Auswertung des Aufrufes "summe 3" ergibt:
summe 3 --> 3 + summe 2 --> 3 + 2 + summe 1 --> 3 + 2 + 1 + summe 0 --> 3 + 2 + 1 + 0 --> 3 + 2 + 1 --> 3 + 3 --> 6
Man erkennt, dass sich der Term zunächst stark aufbläht, bevor er durch die Abbruchbedingung wieder zusammenschrumpft. Ursache dieses Verhaltens ist die Tatsache, dass der letzte Befehl der Funktion summe eine Addition ist.
Wenn es gelingt, eine Funktion so umzuschreiben, dass der rekursive Selbstaufruf die letzte Aktion darstellt, dann spricht man von einer endrekursiven Funktion. Hierzu benötigt man einen Akkumulator (eine weitere Variable), der die Zwischenergebnisse festhält und beim Erreichen der Abbruchbedingung das Endergebnis sofort liefert. Dadurch entfällt das "Zurücklaufen". Zu beachten ist dabei, dass der Akkumulator mit den richtigen Startwerten initialisiert wird.
-- ---------- Akkumulatorlösung ---------- summe 0 x = x summe n x = summe (n-1) (x+n) -- ---------------------------------------
summe 3 0 -- Akkumulator mit 0 vorbelegen --> summe 2 (3) --> summe 1 (5) --> summe 0 (6) --> 6
Beispiele
Beispiel 1
fac’ nicht endrekursiv (ohne pattern matching):
fac’ :: Integer -> Integer fac’ n = if n == 0 then 1 else n * fac’ (n-1)
fac’’ nicht endrekursiv (mit pattern matching):
fac’’ :: Integer -> Integer fac’’ (n+1) = n * fac’’ n fac’’ _ = 1
fac1 endrekursiv (ohne pattern matching):
fac1 :: Integer -> Integer
fac1 n = fac0 n 1 where
fac0 n acc = if n == 0 then acc
else fac0 (n-1) (n*acc)
fac2 endrekursiv (mit pattern matching):
fac2 :: Integer -> Integer
fac2 n = fac0 n 1 where
fac0 n@(m+1) acc = fac0 m (n*acc)
fac0 _ acc = acc
fac’ bzw. fac’’ verbraucht Stackplatz, fac1 bzw. fac2 nicht.
Beispiel 2
Liste umdrehen, nicht endrekursiv:
rev’ :: [a]-> [a] rev’ [] = [] rev’ (x:xs) = rev’ xs ++ [x]
Hängt auch noch hinten an — O(n2)!
Liste umdrehen, endrekursiv in O(n):
rev :: [a]-> [a] rev xs = rev0 xs [] where rev0 [] ys = ys rev0 (x:xs) ys = rev0 xs (x:ys)
Beispiel 3
Nicht endrekursiv:
getLines’ :: IO String
getLines’ = do str<- getLine
if null str then return ""
else do rest<- getLines’
return (str++ rest)
Endrekursiv:
getLines :: IO String
getLines = getit "" where
getit res = do str<- getLine
if null str then return res
else getit (res++ str)
