Rekursion

Das Konzept einer Schleife ist sehr stark mit den Grundideen von imperativen Programmiersprachen verbunden. Eine Schleife ist eine wiederholte Ausführung einer Folge von Anweisungen, die stark auf der Verwendung von veränderbaren Variablen basiert. Daher harmonieren Schleifen nicht sehr gut mit einer rein funktionalen Programmiersprache. Um Wiederholung auszudrücken nutzt man daher in einer rein funktionalen Programmiersprache anstelle einer Schleife Rekursion.

Wir wollen an dieser Stelle schon einmal einen ersten Einblick in das Konzept der Rekursion geben. Da wir bisher aber noch keine Datenstrukturen definieren können, können wir nur vergleichsweise artifizielle rekursive Funktionen definieren. Wenn wir später gelernt haben, wie man rekursive Datenstrukturen definiert, werden wir in der Lage sein, bessere Beispiele zu konstruieren.

Als erstes Beispiel betrachten wir eine Funktion sumTo, die eine Summe von Zahlen berechnet. Der Aufruf sumTo 4 summiert zum Beispiel die Zahlen von 1 bis einschließlich 4, liefert also 1 + 2 + 3 + 4 = 10 als Ergebnis.

sumTo : Int -> Int
sumTo end =
    if end <= 0 then
        0

    else
        end + sumTo (end - 1)

Wenn man versucht, eine rekursive Funktion zu definieren, sollte man folgende Aspekte beachten.

• Die Funktion sollte einen Abbruchfall aufweisen.

In der Definition sumTo ist der Abbruchfall end <= 0. Ein Abbruchfall sorgt dafür, dass die Rekursion beendet wird, die Funktion also terminiert. Falls es keinen Abbruchfall gibt, terminiert die Funktion nicht. Ein Abbruchfall allein ist aber nicht ausreichend, damit eine Funktion terminiert. Neben dem Abbruchfall sollte die Funktion noch so gestaltet sein, dass sie die folgende Eigenschaft erfüllt.

• Ein Argument bewegt sich in Richtung der Abbruchbedingung.

Die folgende fehlerhafte Implementierung terminiert zum Beispiel nicht, obwohl die Funktion einen Abbruchfall besitzt.

sumToWrong : Int -> Int
sumToWrong end =
    if end <= 0 then
        0

    else
        end + sumToWrong (end + 1)

In der Funktion sumToWrong besteht das Problem, dass das Argument end durch die Berechnung end + 1 bei jedem rekursiven Aufruf größer wird und damit ggf. die Bedingung end <= 0 nie erfüllt. Um das Verhalten der Funktion sumToWrong zu illustrieren, wollen wir hier einen Funktionsaufruf auswerten. Als Beispiel betrachten wir den Aufruf sumToWrong 2.

Wichtig

Bei Funktionsanwendungen ist zu beachten, dass Elm als Auswertungsstrategie Call-by Value nutzt.

Das heißt, dass bei einer Funktionsanwendung zuerst die Argumente ausgewertet werden und erst dann die Definition der Funktion eingesetzt wird. Das heißt, bei einem Ausdruck wie sumToWrong (2 + 1) wird zuerst das Argument von sumToWrong ausgewertet, also der Ausdruck 2 + 1 und erst dann wird die Definition von sumToWrong eingesetzt.

Im Folgenden wird angegeben, wie der Ausdruck sumToWrong 2 ausgewertet wird. Wir werden zur Illustration des Verhaltens von Funktionen immer solche Sequenzen von Auswertungsschritten angeben. Das Zeichen = wie es hier verwendet wird, bezeichnet man im Kontext von Programmiersprachen als Definitional Equality. Die Gleichheit bedeutet dabei, dass die Ausdrücke auf beiden Seiten der Gleichheit zum gleichen Ergebnis ausgewertet werden. Bei der Auswertung wird dabei nur eine feste Menge von Regeln angewendet. So können wir zum Beispiel die Definitionen von Funktionen einsetzen. Außerdem können wir die Definitionen von primitiven Funktionen wie + oder <= auf dem Typ Int auswerten.

sumToWrong 2

• =

  if 2 <= 0 then 0 else 2 + sumToWrong (2 + 1)

  Definition von sumToWrong

• =

  if False then 0 else 2 + sumToWrong (2 + 1)

  Definition von <=

• =

  2 + sumToWrong (2 + 1)

  Konditional

• =

  2 + sumToWrong 3

  Definition von +

• =

  2 + (if 3 <= 0 then 0 else 3 + sumToWrong (3 + 1))

  Definition von sumToWrong

• =

  2 + (if False then 0 else 1 + sumToWrong (3 + 1))

  Definition von <=

• =

  2 + (3 + sumToWrong (3 + 1))

  Konditional

• =

  2 + (3 + sumToWrong 4)

  Definition von +

• =

  2 + (3 + (if 4 <= 0 then 0 else 4 + sumToWrong (4 + 1)))

  Definition von sumToWrong

• =

  2 + (3 + (if False then 0 else 4 + sumToWrong (4 + 1)))

  Definition von <=

• =

  2 + (3 + (4 + sumToWrong (4 + 1)))

  Konditional

• =

  2 + (3 + (4 + sumToWrong 5))

  Definition von +

• =

  ...

Die Auswertung des Ausdrucks sumToWrong 2 terminiert nicht, da immer wieder rekursive Aufrufe entstehen, deren Argument noch größer ist. Im Gegensatz dazu sorgt das end - 1 im rekursiven Aufruf der Funktion sumTo dafür, dass end auf jeden Fall irgendwann kleiner gleich 0 ist. Die Tatsache, dass sich ein Argument in Richtung der Abbruchbedingung bewegt, kann bei Funktionen mit einer komplexen Rekursion sehr schwer zu überprüfen sein.

Die Definition sumTo entspricht nicht unbedingt dem Vorgehen, das man erwarten würde, wenn man sich überlegt, wie man die Funktionsweise mithilfe einer Schleife implementieren würde. Wir wollen hier eine weitere Funktionsanwendung auswerten, um das Verhalten zu illustrieren. Als Beispiel betrachten wir in diesem Fall den Aufruf sumTo 2.

sumTo 2

• =

  if 2 <= 0 then 0 else 2 + sumTo (2 - 1)

  Definition von sumTo

• =

  if False then 0 else 2 + sum (2 - 1)

  Definition von <=

• =

  2 + sumTo (2 - 1)

  Konditional

• =

  2 + sumTo 1

  Definition von +

• =

  2 + (if 1 <= 0 then 0 else 1 + sumTo (1 - 1))

  Definition von sumTo

• =

  2 + (if False then 0 else 1 + sumTo (1 - 1))

  Definition von <=

• =

  2 + (1 + sumTo (1 - 1))

  Konditional

• =

  2 + (1 + sumTo 0)

  Definition von +

• =

  2 + (1 + (if 0 <= 0 then 0 else 0 + sumTo (0 - 1)))

  Definition von sumTo

• =

  2 + (1 + (if True then 0 else 0 + sumTo (0 - 1)))

  Definition von <=

• =

  2 + (1 + 0)

  Definition von +

• =

  2 + 1

  Definition von +

• =

  3

  Definition von +

Wichtig

Obwohl Elm Call-by Value nutzt, wird bei einem Konditional nur der erfolgreiche Zweig des Konditionals ausgewertet.

Das heißt, in einem Ausdruck wie if True then 0 else 0 + sumTo (0 - 1) wird der Ausdruck 0 + sumTo (0 - 1) nie ausgewertet, da er für das Ergebnis nicht benötigt wird. Diese Eigenschaft ist sehr wichtig, da die Auswertung des Ausdrucks sumTo 2 ansonsten ebenfalls nicht terminieren würde.

An der Auswertung des Ausdrucks sumTo 2 können wir sehen, dass der Aufruf sumTo 2 die Zahlen in der Reihenfolge 2 + 1 + 0 addiert. Wenn wir eine vergleichbare Methode mithilfe einer Schleife implementieren würden, würden wir vermutlich einen Zähler nutzen, der hochzählt und würden die Zahlen in der Reihenfolge 0 + 1 + 2 addieren. Auch diese Form der Implementierung lässt sich mithilfe von Rekursion umsetzen. Um diese Funktion zu implementieren, benötigen wir allerdings eine Hilfsfunktion. Die Funktion sumToReversed nutzt zur Umsetzung die Hilfsfunktion sumToReversed_.

Wichtig

In Elm nutzt man gern den Suffix _, um zu einem Namen eine Variante zu definieren.

Wenn man zu einer Funktion sumReversed also eine Hilfsfunktion definieren möchte, nutzt man gern den Namen sumReversed_.

Info

In Haskell nutzt man statt _ das Zeichen '. In Elm ist das Zeichen ' als Bestandteil von Bezeichnern nicht erlaubt.

sumToReversed : Int -> Int
sumToReversed end =
    sumToReversed_ 1 end


sumToReversed_ : Int -> Int -> Int
sumToReversed_ counter end =
    if counter > end then
        0

    else
        counter + sumToReversed_ (counter + 1) end

Um diese Form der Implementierung besser zu verstehen, betrachten wir die Auswertung des Ausdrucks sumToReversed 2.

sumToReversed 2

• =

  sumToReversed_ 1 2

  Definition von sumToReversed

• =

  if 1 > 2 then 0 else 1 + sumToReversed_ (1 + 1) 2

  Definition von sumToReversed_

• =

  if False then 0 else 1 + sumToReversed_ (1 + 1) 2

  Definition von >

• =

  1 + sumToReversed_ (1 + 1) 2

  Konditional

• =

  1 + sumToReversed_ 2 2

  Definition von +

• =

  1 + (if 2 > 2 then 0 else 2 + sumToReversed_ (2 + 1) 2)

  Definition von sumToReversed_

• =

  1 + (if False then 0 else 2 + sumToReversed_ (2 + 1) 2)

  Definition von >

• =

  1 + (2 + sumToReversed_ (2 + 1) 2)

  Konditional

• =

  1 + (2 + sumToReversed_ 3 2)

  Definition von +

• =

  1 + (2 + (if 3 > 2 then 0 else 3 + sumToReversed_ (3 + 1) 2))

  Definition von sumToReversed_

• =

  1 + (2 + (if True then 0 else 3 + sumToReversed_ (3 + 1) 2))

  Definition von >

• =

  1 + (2 + 0)

  Konditional

• =

  1 + 2

  Definition von +

• =

  3

  Definition von +

Die Funktion sumToReversed summiert die einzelnen Summanden in der Reihenfolge, die wir aus einer imperativen Sprache ggf. erwarten würden. Wenn wir für die Implementierung tatsächlich eine Schleife nutzen würden, hätten wir aber noch eine zusätzliche lokale Variable, welche in jedem Schleifendurchlauf die aktuelle Summe enthält. Es gibt eine rekursive Variante, die noch ähnlicher zur Implementierung mit einer Schleife ist und diese aktuelle Summe ebenfalls durch eine Variable modelliert. Wir haben schon gelernt, dass man in einer funktionalen Sprache keine Variablen verändern kann. Daher scheint es eigentlich nicht möglich zu sein, das Zwischenergebnis zu modellieren. Obwohl man in einer funktionalen Sprache eine Variable nicht verändern kann, kann man ein ähnliches Verhalten dadurch erzielen, dass immer wieder neue Variablen verwendet werden. Man erreicht dies, indem man die lokale Variable, die in der Schleife immer wieder verändert wird, als weiteres Argument der Funktion modelliert.

Wichtig

Man bezeichnet ein solches Argument als Akkumulatorargument oder Akkumulator, da in diesem Argument das Ergebnis akkumuliert, also angesammelt, wird.

Die Funktion sumToTail_ nutzt einen Akkumulator, um die Summe zu berechnen.

sumToTail : Int -> Int
sumToTail end =
    sumToTail_ 1 0 end

sumToTail_ : Int -> Int -> Int -> Int
sumToTail_ counter acc end =
    if counter > end then
        acc

    else
        sumToTail_ (counter + 1) (acc + counter) end

Das Verhalten der Funktion sumToTail entspricht am ehesten dem Verhalten einer Schleife. Um das Verhalten der Funktion sumToTail zu illustrieren, werten wir die Funktionsanwendung sumToTail 2 aus.

Wichtig

In einer Sprache mit Call-by Value-Auswertung muss noch festgelegt werden, in welcher Reihenfolge die Argumente von Funktionen ausgewertet werden, wenn es mehrere Argumente gibt.

In den allermeisten Fällen werden die Argumente von links nach rechts ausgewertet. In der folgenden Auswertungssequenz wenden wir diesen Umstand an.

sumToTail 2

• =

  sumToTail_ 1 0 2

  Definition von sumToTail

• =

  if 1 > 2 then 0 else sumToTail_ (1 + 1) (0 + 1) 2

  Definition von sumToTail_

• =

  if False then 0 else sumToTail_ (1 + 1) (0 + 1) 2

  Definition von >

• =

  sumToTail_ (1 + 1) (0 + 1) 2

  Konditional

• =

  sumToTail_ 2 (0 + 1) 2

  Definition von +

• =

  sumToTail_ 2 1 2

  Definition von +

• =

  if 2 > 2 then 1 else sumToTail_ (2 + 1) (1 + 2) 2

  Definition von sumToTail_

• =

  if False then 1 else sumToTail_ (2 + 1) (1 + 2) 2

  Definition von >

• =

  sumToTail_ (2 + 1) (1 + 2) 2

  Konditional

• =

  sumToTail_ 3 (1 + 2) 2

  Definition von +

• =

  sumToTail_ 3 3 2

  Definition von +

• =

  if 3 > 2 then 3 else sumToTail_ (3 + 1) (3 + 3) 2

  Definition von sumToTail_

• =

  if True then 3 else sumToTail_ (3 + 1) (3 + 3) 2

  Definition von >

• =

  3

  Konditional

Man bezeichnet rekursive Funktionen, die dem Verhalten einer Schleife ähnlich sind auch als iterative Funktionen. Der Begriff iterative Funktion ist allerdings nicht formal definiert und sollte daher umsichtig verwendet werden.

Wichtig

Die Variante sumToTail hat eine besondere Eigenschaft, sie ist endrekursiv (Tail Recursive).

Endrekursive Funktionen sind in der funktionalen Programmierung von speziellem Interesse. Wenn der Compiler eine Optimierung umsetzt, die Tail-Call Optimization (TCO) genannt wird, kann eine endrekursive Funktion ohne den Verbrauch von Stack-Speicher ausgeführt werden. Für die Ausführung einer rekursiven Funktion wird ansonsten immer Speicher auf dem Stack benötigt. Auf dem Stack wird gespeichert, an welcher Stelle die Berechnung fortfahren muss, wenn der rekursive Aufruf beendet ist.

Wichtig

Endrekursive Funktionen können zwar ggf. effizienter sein, nicht-endrekursive Funktionen sind in der funktionalen Programmierung aber in vielen Fällen idiomatischer.

Daher sollte man in den meisten Fällen die nicht-endrekursive Variante vorziehen. Außerdem sind nicht alle endrekursiven Funktionen automatisch effizienter. Wir werden in einem späteren Kapitel eine Funktion kennenlernen, deren natürliche Implementierung eine lineare Laufzeit hat. Die endrekursive Variante hat aber eine quadratische Laufzeit und ist damit wesentlich ineffizienter.

• zurück
• Inhaltsverzeichnis
• weiter