Rekursion

Rekursion

Rekursion bezeichnet eine Technik, bei der sich eine Methode **selbst aufruft**, um ein Problem in kleinere Teilprobleme zu zerlegen. Ein rekursiver Aufruf wiederholt sich so lange, bis ein klar definierter **Abbruchfall** erreicht wird – dieser verhindert unendliche Schleifen.

Rekursion eignet sich besonders für Aufgaben, die sich natürlich in gleichartige Teilprobleme zerlegen lassen, z. B. Bäume durchsuchen, Dateien in Ordnern durchlaufen oder mathematische Folgen berechnen.

Aufbau einer rekursiven Methode

Eine rekursive Methode besteht immer aus zwei Teilen:

1. **Abbruchfall** – beendet die Rekursion 2. **Rekursiver Aufruf** – löst einen kleineren Teil des Problems

Beispiel: Fakultät berechnen

public int fakultaet(int n) {
    if (n == 0) {
        return 1;               // Abbruchfall
    }
    return n * fakultaet(n - 1); // Rekursiver Aufruf
}

Beispiel: Summe eines Arrays

public int summe(int[] arr, int index) {
    if (index == arr.length) {
        return 0;
    }
    return arr[index] + summe(arr, index + 1);
}

Vorteile

• eleganter Code für rekursive Probleme
• natürliche Darstellung hierarchischer Strukturen
• weniger komplexe Schleifen notwendig

Nachteile

• kann zu Stackoverflow führen, wenn kein Abbruchfall erreicht wird
• oft langsamer als iterative Lösungen
• schwerer zu debuggen

Kurzmerksatz

Rekursion löst Probleme, indem sich eine Methode selbst mit kleineren Teilproblemen aufruft, bis ein Abbruchfall erreicht wird.