Rekursion ist für manche noch ein ungewohntes Konzept. Viele einfache Aufgaben lassen sich aber direkt nach „Schema F“ lösen. Der generelle Ansatz ist eigentlich immer gleich. Deshalb hier ein paar kleine Daumenregeln, die vielleicht helfen, Rekursionsaufgaben systematischer zu lösen:
Analogie: Vollständige Induktion
Rekursion funktioniert so ähnlich wie vollständige Induktion. Bei letzterer gibt es einen Induktionsanfang, eine Induktionsvoraussetzung und einen Induktionsschritt. Ganz ähnlich ist es mit der Rekursion: Ein Rekursionsanfang definiert die Funktion für den einfachsten Fall (beispielsweise die leere Liste). Dann kann angenommen werden, dass die Funktion bereits funktioniert (der rekursive Aufruf nutzt das). Schließlich ist analog zum Induktionsschritt ein Rekursionsschritt nötig. Dabei wird quasi nur noch das implementiert, was getan werden muss, wenn die Liste um ein Element länger ist.
Die Datenstruktur bestimmt die Rekursion
Die meisten Rekursionsaufgaben orientieren sich an bestimmten rekursiven Datenstrukturen. Das sind in den meisten Fällen entweder Listen oder Bäume. Die Lösung der Aufgabe wird demnach stark an die Definition der Datenstruktur angelehnt sein.
Listen
Handelt es sich bei der Datenstruktur um eine Liste, sieht der Ansatz in den meisten Fällen folgendermaßen aus:
1 2 3 | myfunc :: [...] -> ... myfunc [] = [] -- Rekursionsanfang: Leere Liste myfunc (x:xs) = ... -- Rekursionsschritt: Kopf der Liste und der Rest |
Bäume in Haskell
Bei Bäumen sieht es ganz ähnlich aus. Dabei kommt es aber etwas auf die Definition der Datenstruktur an Hier zwei IMHO gängige Varianten:
1 2 3 4 5 6 | {- Ein Binärbaum ist entweder ein einzelnes Blatt oder ein Knoten, der mit zwei Teilbäumen verbunden ist. -} data BinTree1 = Leaf Integer | Node BinTree1 Integer BinTree1 -- linker Teilbaum, Markierung, rechter Teilbaum deriving (Eq, Ord, Show) |
Es ist natürlich auch möglich, andere Typen für die Markierung zu haben, sowie Blätter und innere Knoten unterschiedlich oder auch gar nicht zu markieren.
Ebenso ist es möglich, einen „Empty“-Wert zu definieren. Damit wären Blätter einfach nur Knoten, die zwei Empty-Werte als Kinder haben:
1 2 3 4 5 6 | {- Ein Binärbaum ist entweder leer oder ein Noten, der über zwei (ggf. leere) Teilbäume verfügt. -} data BinTree2 = Empty -- leerer Baum | Node BinTree2 Integer BinTree2 -- linker Teilbaum, Markierung, rechter Teilbaum deriving (Eq, Ord, Show) |
Die zweite Definition hat den Vorteil, dass man damit auch leere, sowie zu Listen entartete Bäume darstellen kann.
Rekursion auf Binärbäumen sieht in den meisten Fällen so aus:
1 2 3 | myfunc :: Bintree1 -> ... myfunc (Leaf m) = ... myfunc (Node l m r) = ... |
bzw.
1 2 3 | myfunc :: BinTree2 -> ... myfunc Empty = ... myfunc (Node l m r) = ... |
Wenn also Rekursion auf Listen oder Bäumen verlangt ist, ist der Anfang in den meisten Fällen klar.
Weitere Fälle
Weitere Fälle benötigt man, wenn man diese explizit anders behandeln muss (beispielsweise wie in Blatt 5 Aufgabe 5e) „eval“) oder, wenn man mehr Daten gleichzeitig verarbeiten muss (beispielsweise, wenn man in einer Liste benachbarte Elemente miteinander verrechen muss).
Dabei ist es u.U. nötig, weitere „Rekursionsanfänge“ zu definieren:
1 2 3 4 5 6 7 | {- Diese Funktion nimmt eine Liste und vertauscht je zwei benachbarte Werte miteinander. -} swapNeighbors :: [a] -> [a] swapNeighbors [] = [] -- leere Liste swapNeighbors [a] = [a] -- einelementige Liste swapNeighbors (first:second:rest) = second:first : (swapNeighbors rest) |
Hier ist der mittlere Fall, die einelementige Liste, notwendig, da das Pattern (first:second:rest) nicht auf diese matcht. Im „Normalfall“ sind solche weiteren Rekursionsanfänge aber nicht nötig.
Der Rekursionsschritt
Nachdem der Rekursionsanfang (die leere Liste, das einzelne Blatt, der leere Baum) behandelt wurde, geht es nun an den Rekursionsschritt. Hier geschieht die eigentliche Arbeit. Alles, was bisher beschrieben wurde, ist fast immer gleich.
Auf den Rekursionsschritt gibt es mehrere Sichtweisen. Zwei davon sind oft recht hilfreich:
1. Wenn sich die Aufgabe für ein (oder zumindest wenige) Elemente separat betrachten lässt, was insbesondere bei map-ähnlichen Funktionen der Fall ist, betrachtet man ab besten diese Aufgabe auch getrennt. Der Rekursionsaufruf kann dann als „und mach dann das selbe für den Rest“ verstanden werden. Vergleiche hierzu die swapNeighbors-Funktion oben.
2. Ist das nicht so einfach möglich, so betrachte den rekursiven Aufruf als schon fertigen Teil der Aufgabe. So ähnlich wie die Induktionsvoraussetzung bei der Induktion. Typisches Beispiel hierfür wäre InsertionSort.
1 2 3 | insertionSort :: (Ord a) => [a] -> [a] insertionSort [] = [] insertionSort (x:xl) = insert x (insertionSort xl) |
Hier ist es leichter, sich vorzustellen, dass (insertionSort xl) bereits eine sortierte Liste ist. Nun muss man sich nur noch überlegen, was man tun muss, wenn man eine um ein Element längere Liste hat. In diesem Fall muss man ganz einfach dieses eine Element in die bereits sortierte Liste einfügen. Und genau das tut der obige Code.
Zusätzliche Parameter
Zusätzliche Parameter braucht man vor allem dann, wenn man so etwas wie einen Zustand simulieren will. Ein Beispiel hierfür wäre die istKetteStern-Funktion (Blatt 4 Aufgabe 5d). Hier muss sich die Funktion merken, ob bereits ein Stern gefunden wurde oder noch nicht. Deshalb ist der zusätzliche Bool-Parameter notwendig. In so einem Fall ist es meist sehr sinnvoll den Sinn des zusätzlichen Parameters in einem Kommentar zu beschreiben.
Die eigentlich zu implementierende Funktion soll diesen Parameter dann aber nicht haben und so bildet diese nur einen Wrapper um die neue Funktion:
1 2 3 4 5 6 7 8 9 | istKetteStern :: [Char] -> Bool istKetteStern kette = istKetteSternHelper kette False where -- der zusätzliche Bool-Parameter zeigt an, ob der '*' bereits gefunden wurde istKetteSternHelper :: [Char] -> Bool -> Bool istKetteSternHelper [] found = found istKetteSternHelper ('*':rest) True = False -- ein zweiter Stern ist ein Stern zu viel istKetteSternHelper ('*':rest) False = istKetteSternHelper rest True -- jetzt ist der '*' gefunden istKetteSternHelper (x:xs) found = istGross x && istKetteSternHelper xs found |
Das gleiche Prinzip kann man sich zunutze machen, um quasi Zwischenergebnisse dort „abzulegen“. Damit kann man Implementierungen effizienter machen. Das ist dann aber meist ein zweiter Schritt, der gemacht wird, wenn eine bereits bestehende Funktion auf diese Weise optimiert werden soll.
Zusätzliche Funktionen, die etwas anderes tun, als die Ausgangsfunktion (beispielsweise insert im obigen InsertionSort-Beispiel, können aber unabhängig von solchen Überlegungen sinnvoll sein. Als Daumenregel könnte man sich hier definieren, dass man sich den Einsatz einer zusätzlichen Funktion überlegen sollte, wenn man einer solchen leicht einen passenden Namen geben könnte. Bei insert im obigen Fall ist das beispielsweise so. Umgekehrt heißt das wiederum, dass eine zusätzliche Funktion vielleicht nicht notwendig ist, wenn man Probleme hat, diese sinnvoll zu benennen. Letztere Daumenregel steht aber auf wackligen Füßen. Je nach Komplexität des Algorithmus kann auch so etwas vorkommen.
Weitere Hinweise
- Die Funktion
lengthbenötigt man i.d.R. recht selten. - Pattern Matching macht rekursive Funktionen deutlich übersichtlicher.
Das, was ich hier schreibe ist inoffizielles Zusatzmaterial. Es kann euch vielleicht für die Klausur (und/oder darüber hinaus) helfen, aber ihr werdet euch vermutlich nicht darauf berufen können. Im Zweifel gilt nicht das, was hier steht, sondern das Skript bzw. die Vorlesung.
Anmerkungen jeglicher Art sind gerne gesehen. Persönlich, per Mail oder auch als Blog-Kommentar. Wie immer gilt: Bei Fragen: fragen.