Rekursion in Java

In der Informatik bezeichnet Rekursion eine Prozedur oder Funktion, welche sich selbst mit geänderten Übergabeparametern immer wieder aufruft, bis eine zuvor definierte Abbruchbedingung erfüllt ist.

Grundprinzip

Die Rekursion wird oft als Königsdisziplin der Programmierung bezeichnet, da sie für viele zunächst verwirrend und kompliziert erscheint. Dabei beruht die Rekursion auf einem simplen Konzept, welches dir vielleicht schon bekannt ist:

Ein kleines Beispiel für dieses Prinzip: Du hast für eine Schulaufgabe viel zu lernen. Statt zu versuchen, alles auf ein Mal zu lernen, teilst du den Stoff in Lernpakte ein. Dies machst du so lange, bis ein Lernpaket einen Umfang von ca. 1h hat und somit bewältigbar ist. Statt mit dem ganzen Stoffumfang auf einmal überwältigt zu sein, hast du nun viele kleine Teile, die schaffbar sind. Am Schluss ergibt die Summe aller Lernpakte wieder das große Ganze.

Rekursion in Java implementieren

Die Rekursion nutzt nun genau dieses Prinzip aus. Schau dir das folgende Beispiel für Rekursion in Java an, mit der du die Fakultät einer Zahl berechnen kannst. Bedenke: Die Fakultät einer Zahl ist das Produkt aller natürlichen Zahlen kleiner oder gleich der Zahl. Also für 4 wäre die Fakultät 4 x 3 x 2 x 1 = 24.

Java behält bei der Rekursion mithilfe des Aufrufgrafen den Überblick. Der Aufrufgraf ist dabei ein Stack, welcher dem Programm dabei hilft zu erkennen, an welcher Stelle im Programmablauf es sich befindet.

Bei jedem Aufruf einer Methode wird dieser Aufruf im Stack abgelegt. Mit jedem weiteren Selbstaufruf der Methode wird ein neues Element im Stack oben eingeordnet (linke Seite der unteren Grafik).

Konkret sieht der Ablauf des Aufrufes der Methode calculateFactorial so aus:

1. Die Funktion calculateFactorial(int number) berechnet die Fakultät der Variable number.

2. Dabei wird geprüft, ob der Wert der Variable number gleich 1 ist.

3. Wenn dies der Fall ist, so wird 1 zurück gegeben. Weshalb dies wichtig ist, siehst du später noch.

4. Wenn der Wert nicht gleich 1 ist, so wird die Methode calculateFactorial erneut aufgerufen, dieses Mal jedoch mit number - 1.

5. Dies geschieht so lange, bis der erste Fall (number == 1) eintritt. Daraufhin läuft der Aufrufgraf der Methode zurück und wird wieder abgebaut.

6. Beim Abbau werden die Zwischenergebnisse multipliziert, bis im letzten Schritt das Gesamtergebnis zurückgegeben wird.

Abgrenzung zur Iteration

Im Gegensatz zur Iteration ruft sich bei der Rekursion eine Methode selbst auf. Merke:

Direkte vs. Indirekte Rekursion

Bei der direkten Rekursion ruft sich eine Methode immer wieder selbst auf.

Dagegen spricht man von der indirekten Rekursion, wenn eine Methode A eine Methode B aufruft, welche wiederum noch andere Methoden aufrufen kann, welche jedoch wieder irgendwann die Methode A aufrufen.

Also zum Beispiel:

Methode A ruft Methode B auf, welche Methode C aufruft, welche wiederum Methode A aufruft, usw., bis eine Abbruchbedingung eintritt.

Beispiel

Jan möchte ein Programm schreiben, welches ihm Wörter rückwärts ausgibt. Dafür benötigt er das Prinzip der Rekursion.

Das Programm soll einen String name annehmen. Von diesem String soll die Methode backwards bei jedem Aufruf den letzten Buchstaben abschneiden und behalten. Dies geschieht durch den Code name.substring(name.length()-1) .

Anschließend soll die Methode sich immer wieder selbst mit dem Wort ohne den letzten Buchstaben aufrufen, bis das Wort aus nur noch einem einzigen Buchstaben besteht. Den Teil eines Wortes ohne den letzten Buchstaben erhält man durch name.substring(0,name.length()-1).

Insgesamt sieht Jan's Programm so aus:

Der rekursive Aufruf lastLetter + backwards(rest) sorgt dafür, dass alle Buchstaben in umgekehrter Reihenfolge aneinander gehängt werden. Und schon kann Jan sich Wörter rückwärts ausgeben lassen. In obigem Beispiel wird aus "simpleclub" übrigens "bulcelpmis".