Java-Rekursion: Verständnis, Beispiele und Vor-/Nachteile

Java-Rekursion

Dieser Leitfaden erklärt Javas rekursive Methoden, geht am klassischen Fakultäts-Beispiel durch und bewertet Vor- und Nachteile der Rekursion.

In Java wird eine Methode, die sich selbst aufruft, als rekursive Methode bezeichnet, und die Gesamtheit der Technik heißt Rekursion. Eine einfache Realwelt-Illustration sind zwei sich gegenüberstehende Spiegel: Jede Reflexion ist ein weiteres Spiegelbild, das sich wiederholt, bis das Licht absorbiert wird.

---

Wie Rekursion funktioniert

In der obigen Illustration wird die rekursiv()-Methode von main() aufgerufen – ein normaler Aufruf. Innerhalb von rekursiv() ruft dieselbe Methode sich selbst wieder auf, was einen rekursiven Aufruf erzeugt. Um endloses Schleifen zu verhindern, muss jeder rekursive Aufruf eine Abbruchbedingung enthalten, typischerweise implementiert mit einer if…else-Anweisung.

---

Beispiel: Fakultät einer Zahl mit Rekursion

class Fakultät { static int fakultaet(int n) { if (n != 0) // Abbruchbedingung return n * fakultaet(n - 1); // rekursiver Aufruf else return 1; } public static void main(String[] args) { int zahl = 4, ergebnis; ergebnis = fakultaet(zahl); System.out.println(zahl + " Fakultät = " + ergebnis); } }

Ausgabe:

4 Fakultät = 24

Die fakultaet()-Methode wird von main() mit dem Argument zahl aufgerufen. Innerhalb von fakultaet() bewirkt die Zeile

return n * fakultaet(n-1);

dass die Methode sich selbst mit einem dekrementierten Wert aufruft. Beginnend mit n = 4 verlaufen die Aufrufe: 4 → 3 → 2 → 1 → 0. Wenn n 0 erreicht, schlägt die if-Bedingung fehl und gibt 1 zurück. Das akkumulierte Produkt propagiert dann zurück den Aufrufstapel hinauf zu main().

---

Wie das Fakultäts-Programm ausgeführt wird

Das folgende Bild veranschaulicht die Entwicklung des Aufrufstapels während der Ausführung.

---

Vor- und Nachteile der Rekursion

• Vorteile: Vereinfacht Code für Probleme, die natürlicherweise rekursive Muster aufweisen (z. B. Baumdurchläufe, kombinatorische Erzeugung). Führt oft zu kürzeren, lesbareren Implementierungen.
• Nachteile: Jeder rekursive Aufruf verbraucht Stack-Speicher; tiefe Rekursion kann zu Stack Overflow führen. Rekursive Lösungen sind typischerweise weniger speichereffizient und können langsamer sein als iterative Gegenstücke.

Insgesamt bietet Rekursion elegante Lösungen auf Kosten höherer Speichernutzung und potenzieller Performance-Einbußen. Für viele Anwendungsfälle, besonders solche mit begrenzter Tiefe, ist der Trade-off lohnenswert.

Weiterführende Lektüre: Was sind die Vor- und Nachteile der Rekursion?