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 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.

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.