Fachkonzept - Rekursion
Ein Beispielkontext
Die Grundidee der Rekursion wird hier am Beispiel des Begrüßungsproblems verdeutlich: In einem Raum befindet sich eine bestimmte Anzahl von Personen. Jede Person soll jede andere Person begrüßen. Wie viele Begrüßungen finden dann statt?
Wir beschreiben das Begrüßungsproblem mit einer Übergabe-Rückgabe-Situation.
Übergabe: - Anzahl der Personen: 4 Rückgabe: - Anzahl der Begrüßungen: 6
Die Anzahl von Begrüßungen soll mit einer Funktion anzahlBegruessungen
bestimmt werden.
Signatur:
anzahlBegruessungen: Int -> Int
Beispiele:
anzahlBegruessungen 4 -> 6
Die Grundidee
Das Begrüßungsproblem lässt sich mit Hilfe einer Problemreduktionsstrategie lösen. Man führt das Problem auf ein entsprechendes in verkleinerter Form zurück.
Oft ist es günstig, sich Problemreduktionschritte am Beispiel anzuschauen.
Rekursionsschritt bzw. Rückführungsschritt - Beispiel:
anzahlBegruessungen 4 -> (anzahlBegruessungen 3) + 3
Ein solcher Rückführungsschritt muss korrekt in dem Sinne sein, dass der Ausdruck nach dem Rückführungsschritt denselben Wert wie der Ausdruck vor dem Rückführungsschritt hat.
Mit solchen Rückführungsschritten gelangt man zu einem Rückführungsanfang, bei dem man das Ergebnis direkt angeben kann:
Rekursionsanfang bzw. Rückführungsanfang - Beispiel:
anzahlBegruessungen 1 -> 0
Auch dieser Schritt muss natürlich korrekt sein.
Wir verallgemeinern diese Betrachtungen mit Hilfe von Problemreduktionsregeln.
Rekursionsanfang bzw. Rückführungsanfang - allgemein:
Falls anzahlPersonen == 1:
anzahlBegruessungen anzahlPersonen -> 0
Rekursionsschritt bzw. Rückführungsschritt - allgemein:
Falls anzahlPersonen > 1:
anzahlBegruessungen anzahlPersonen -> (anzahlBegruessungen (anzahlPersonen-1)) + (anzahlPersonen-1)
Mit Hilfe dieser Reduktionsregeln lässt sich jetzt das Begrüßungsproblem für jede (sinnvolle) Anzahl von Personen lösen. Man muss den Rekursionsschritt nur immer wieder anwenden, bis man zum Rekursionsanfang gelang.
anzahlBegruessungen 6 -> (anzahlBegruessungen 5) + 5 -> ((anzahlBegruessungen 4) + 4) + 5 -> (((anzahlBegruessungen 3) + 3) + 4) + 5 -> ((((anzahlBegruessungen 2) + 2) + 3) + 4) + 5 -> (((((anzahlBegruessungen 1) + 1) + 2) + 3) + 4) + 5 -> ((((0 + 1) + 2) + 3) + 4) + 5 -> (((1 + 2) + 3) + 4) + 5 -> ((3 + 3) + 4) + 5 -> (6 + 4) + 5 -> 10 + 5 -> 15
Die hier verwende Problemlösestrategie lässt sich so charakterisieren.
Rekursive Problemreduktion ist eine Problemlösestrategie, bei der ein Problem
auf ein strukturgleiches Problem in verkleinerter
Form zurückgeführt wird.
Man beschreibt die Problemreduktion mit Hilfe von Rekursionsschritten und einem Rekursionsanfang.
Implementierung der Grundidee
Mit Hilfe des Rekursionsanfangs und des Rekursionsschritts lässt sich direkt eine Funktionsdefinition für die Funktion anzahlBegruessungen
erstellen.
Beachte, dass die Funktion im Funktionsausdruck selbst aufgerufen wird.
Es handelt sich um eine rekursive Funktionsdefinition.
anzahlBegruessungen: Int -> Int
anzahlBegruessungen anzahlPersonen =
if anzahlPersonen == 1 then
0
else
(anzahlBegruessungen (anzahlPersonen-1)) + (anzahlPersonen-1)
Eine rekursive Funktionsdefinition ruft sich (eventuell über Umwege) selbst auf und nutzt sich so selbst zur Festlegung der Verarbeitung.
Diese Art der Funktionsdefinition ist (in der Regel) nur dann sinnvoll,
wenn bei den Selbstaufrufen tatsächlich Reduktionsschritte durchgeführt werden, d.h. wenn die Funktion
sich nur in verkleinerter
Form aufruft, wobei der Verkleinerungsprozess
nach endlich vielen Schritten zu einem Rekursionsanfang führen muss. Dieser Rekursionsangfang muss
dann direkt beschrieben werden.
Um Rekursion als Berechnungsstrategie nutzen zu können, benötigt man ein Ausführsystem wie Elm, das in der Lage sind, rekursive Funktionsdefinitionen wiederholt aufzurufen und auf diese Weise das eigentliche Berechnungsergebnis zu generieren.
Rekursion ist eine mächtige und gerne genutzte Strategie beim Problemlösen. Wenn der Problemkontext es zulässt, dann kann man das Problemlöseverfahren sehr einfach und kompakt über eine Problemreduktion beschreiben. Die wiederholte Ausführung der Reduktionsschritte - und damit die Erzeugung der eigentlichen Lösung - überlässt man dem Ausführsystem.