Programmieren

Umwandlung von Rekursion in Endrekursion

In der funktionalen Pro­grammierung werden Funktionen vielfach rekursiv definiert. Rekursion allerdings verursacht im Allgemeinen einen hohen Verwaltungs­aufwand, da jeder rekursive Aufruf einen neuen Eintrag im Aufrufstack erzeugt. In vielen Fällen, wenn die Rekursions­tiefe zu groß wird, kommt es sogar zu einem Überlauf des Stacks (engl.: stack overflow).

Bei der sogenannten Endrekursion (engl.: tail recursion) dagegen kann der jeweils letzte Eintrag im Aufrufstack wieder­verwendet werden, da er nicht mehr benötigt wird. Ein Überlauf des Stacks ist somit nicht möglich.

Mithilfe eines Iterations­schemas lassen sich einerseits Programm­schleifen, andererseits aber auch endrekursive Funktionen entwerfen.

Eine andere Möglichkeit, die sich in bestimmten Fällen anwenden lässt, ist die formale Umwandlung einer rekursiven Funktion in eine ent­sprechende endrekursive Funktion. Dieses Verfahren wird im Folgenden in der funktionalen Programmier­sprache Haskell anhand von Beispielen dargestellt.

Formale Manipulation der Umwandlung

Gegeben ist eine rekursive Haskell-Funktion der folgenden Form

f x  | b x       = h x
     | otherwise = o (f (k x)) (i x)

Hierbei ist der Funktions­wert ein Element eines Monoids mit der Verknüpfung o, d.h. die Funktion o ist assoziativ, und das Element e ist das neutrale Element.

Der Ausdruck h x bildet das Rekursions­ende, wenn die Bedingung b x eintritt. Ansonsten wird die Funktion f mit dem Argument k x rekursiv aufgerufen und mit i x verknüpft.

Diese Funktion f wird in eine endrekursive Version f ' wie folgt umgewandelt. Endrekursion ist in der funktionalen Pro­grammierung die Entsprechung zu Iteration. Daher ist die hier verwendete Hilfs­funktion mit iterate bezeichnet.

f' x = iterate x e
    where
    iterate x y | b x       = o (h x) y
                | otherwise = iterate (k x) (o (i x) y)

Beispiele

Als erstes Beispiel betrachten wir die Fakultäts­funktion. Der Funktions­wert ist ein Element aus dem Monoid (ℕ0, ·, 1).

-- Fakultätsfunktion
fac x  | x==0      = 1
       | otherwise = fac (x-1) * x

Hierbei gelten die Ent­sprechungen

f x    fac x
b x    x==0
h x    1
o      *
k x    x-1
i x    x
e      1

Dies führt zu folgender end­rekursiven Version:

fac' x = iterate x 1
    where
    iterate x y | x==0      = 1 * y
                | otherwise = iterate (x-1) (x*y)

 

Als weiteres Beispiel betrachten wir die Funktion len zur Bestimmung der Länge einer Liste. Der Funktions­wert ist ein Element aus dem Monoid (ℕ0, +, 0).

-- Länge einer Liste
len x  | null x    = 0
       | otherwise = len (tail x) + 1

Hierbei gelten die Ent­sprechungen

f x    len x
b x    null x
h x    0
o      +
k x    tail x
i x    1
e      0

Dies führt zu folgender end­rekursiven Version:

len' x = iterate x 0
    where
    iterate x y | null x    = 0 + y
                | otherwise = iterate (tail x) (1 + y) 

Aufgaben

Aufgabe 1:  Überführen Sie die folgende rekursive Funktion zum Aufsummieren einer Liste von Zahlen in eine ent­sprechende endrekursive Version.

-- Aufsummieren einer Liste
summe x  | null x    = 0
         | otherwise = summe (tail x) + head x

Lösung:  

Es gelten die Ent­sprechungen

f x   summe x
b x   null x
h x   0
k x   tail x
o     +
i x   head x
e     0

Dies führt zu folgender end­rekursiven Version:

summe' x = iterate x 0
    where
    iterate x y | null x    = 0 + y
                | otherwise = iterate (tail x) (head x + y)

 

 

 

[up]

 

H.W. Lang   mail@hwlang.de   Impressum   Datenschutz
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden