Rekursion

Einführung

Rekursion stammt aus dem Lateinischen und bedeutet "das Zurücklaufen" (Duden). Die Rekursion ist eine sich selbst aufrufende Funktion. In der Java Programmierung nennt man Funktionen Methoden. In diesem Kontext handelt es sich also um selbstaufrufende Methoden. Die Rekursion ist ein Werkzeug, um komplexe Algorithmen zu entwickeln. Jeder Algorithmus, der sich mit einer Schleife abbilden lässt, lässt sich auch mit Rekursion abbilden, aber nicht umgekehrt.

Wichtig bei der rekursiven Programmierung ist die Definition einer Abbruchbedingung in der sich selbstaufrufenden Funktion. Diese Abbruchbedingung wird auch Rekursionsanker genannt. Ohne Abbruchbedingung würde sich das rekursive Programm theoretisch unendlich oft selbst aufrufen.

Rekursion stellt für viele Programmiereinsteiger am Anfang eine Herausforderung dar. Dennoch ist es wichtig, die Rekursion zu verstehen und auch anwenden zu können, da man mit ihrer Hilfe einige Problemfälle sehr elegant Lösen kann. Dies ist z.B. beim Quicksort der Fall.

Beispiel

Ein Beispiel für die Verwendung einer rekursiven Programmierung ist die Berechnung der Fakultät einer Zahl. Die Fakultät ist das Produkt aller ganzen Zahlen von 1 bis zu dieser Zahl. Die Fakultät von 4 ist also

.

Der rekursive Algorithmus lässt sich wie folgt beschreiben:

• Will man die Fakultät von 4 berechnen, so muss man zunächst die Fakultät von 3 berechnen und das Ergebnis mit 4 multiplizieren.

• Will man die Fakultät von 3 berechnen, so muss man zunächst die Fakultät von 2 berechnen und das Ergebnis mit 3 multiplizieren.

• Will man die Fakultät von 2 berechnen, so muss man zunächst die Fakultät von 1 berechnen und das Ergebnis mit 2 multiplizieren.

• Will man die Fakultät von 1 berechnen, so muss man zunächst die Fakultät von 0 berechnen und das Ergebnis mit 1 multiplizieren.

• Die Fakultät von 0 ist nach Definition 1.

• Die Fakultät von 1 ist also 1*1=1

• Die Fakultät von 2 ist also 1*1*2=2

• Die Fakultät von 3 ist also 1*1*2*3=6

• Die Fakultät von 4 ist also 1*1*2*3*4=24

In einer Sprache wie Java, die rekursive Programmierung zulässt, kann man die Fakultät folgendermaßen eingeben:

public int fakultät(int n){

if(n>1){

// bevor n mit der Rückgabe von berechneFakultaet multipliziert wird, wird berechneFakultaet erneut aufgerufen

// Solange bis n<=1; Dies ist die Abbruchbedingung

return(n*fakultät(n-1));

}else{

// Fakultät von 0 und 1 liefert immer 1

return (1);

}

}

Veranschaulichen lässt sich die Rekursion am Beispiel der Fakultät auch an Hand der folgenden Darstellung. Ruft man die Methode fakultät(4) auf, so wird als Eingabeparameter n=4 übergeben. Dieser Aufruf ist Aufruf Nummer 1. Es folgen drei weitere Aufrufe der Methode fakultät(n), um die Fakultät vom Wert 4 zu berechnen. Im vierten und letzten Aufruf hat die Variable n den Wert 1 angenommen. Die Abbruchbedingung ist erfüllt. Nun werden die Methodenaufrufe - symbolisiert durch die Pfeile - nacheinander abgearbeitet. Durch dieses nachträgliche Abarbeiten, wird die latinische Bedeutung des Wortes Rekursion ersichtlich: recursio = das Zurücklaufen.

Die Reihenfolge kann in BlueJ auch anhand der Call Sequenz im Debugger nachvollzogen werden.