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.

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)

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.