Fachkonzept - Rekursive Funktionsdefinition
Rekursive Problemreduktion
Als Beispiel betrachten wir die Berechnung der Summe aufeinander folgender natürlicher Zahlen, wie z.B.:
summe(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15
Solche Berechnungen sollen mit Hilfe einer Funktion summe
erfolgen.
Solche Berechnungen lassen sich mit Hilfe von Problemreduktionsschritten beschreiben:
summe(4) -> summe(3) + 4
Will man beispielsweise summe(4)
bestimmen, so reicht es,
summe(3)
zu bestimmen und die 4 noch hinzu zu addieren.
Hier wird das Berechnungsproblem summe(4)
auf ein entsprechendes Berechnungsproblem
summe(3)
reduziert.
Diese Strategie, ein Berechnungsproblems auf ein entsprechendes Berechnungsproblem zu reduzieren,
ist immer anwendbar, sofern die übergebene Zahl größer als 0 ist. Im Fall
summe(0)
muss man das Ergebnis dann direkt angeben:
summe(0) -> 0
Ein Berechnungsablauf lässt sich jetzt mit einer Reduktionskette (d.h. einer Folge von Reduktionsschritten) beschreiben:
summe(4) -> summe(3) + 4 -> (summe(2) + 3) + 4 -> ((summe(1) + 2) + 3) + 4 -> (((summe(0) + 1) + 2) + 3) + 4 -> (((0 + 1) + 2) + 3) + 4 -> ((1 + 2) + 3) + 4 -> (3 + 3) + 4 -> 6 + 4 -> 10
Bei der Berechnung haben wir eine Strategie benutzt, die man als rekursiv (d.h. zurücklaufend) bezeichnet.
Rekursive Problemreduktion ist eine Problemlösestrategie, bei der ein Problem
auf ein strukturgleiches Problem (in verkleinerter
Form) zurückgeführt wird.
Rekursive Funktionen
Die oben gezeigten (exemplarischen) Reduktionsschritte lassen sich zu einer Funktionsdefinition verallgemeinern.
def summe(n):
if n == 0:
ergebnis = 0
else:
ergebnis = summe(n-1) + n
return ergebnis
Beachte, dass die zu definierende Funktion in der Funktionsdefinition selbst aufgerufen wird.
Eine rekursive Funktionsdefinition ruft sich (eventuell über Umwege) selbst auf und nutzt sich so selbst zur Definition 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, das in der Lage sind, rekursive Funktionsdefinitionen wiederholt aufzurufen und auf diese Weise das eigentliche Berechnungsergebnis zu generieren. Alle gängigen Programmiersysteme erlauben eine Implementierung rekursiver Funktionen.
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.
Die folgende Visualisierung verdeutlicht, wie Python (als Ausführsystem) rekursive Funktionsaufrufe verarbeitet.