Rekursion

Worum geht´s?

Methoden können von der main-Methode aus aufgerufen werden. Sie können auch von anderen Methoden aufgerufen werden. Ein Sonderfall ist es jedoch, wenn eine Methode sich selbst aufruft: Man nennt das dann Rekursion.

Rekursion ist eine besondere Technik in der Programmierung, mit der Algorithmen möglich sind, die mit Hilfe von Schleifen zwar oft auch möglich sind, aber um einiges komplizierter.

1. Welche Probleme sich gut für rekursive Lösungen eignen

Rekursive Lösungen sind immer dann sinnvoll, wenn ein Problem 3 Eigenschaften hat:

1. Es gibt einen Teil-Lösungsschritt, den wir lösen können
2. Nach dem Teil-Lösungsschritt sind wir der Lösung zumindest ein kleines Stück näher
3. Wir wissen, wann wir aufhören sollen

Ein sehr einfaches Beispiel für eine rekursive Lösung könnte es z.B. sein, dass wir eine Methode schreiben wollen, die uns von einer beliebigen Zahl rückwärts bis 0 zählt (z.B. für ein Kinderspiel, wo ein Kind die Augen zu hat und herunterzählt, bevor es die anderen fängt). Das könnten wir als Schleife ohne Rekursion so lösen:

public static void main(String[] args) {
    countDown(10);
}

public static void countDown(int x) {
    for (int i = x; i >= 0; i--) {
        System.out.println(i);
    }
}

Die selbe Aufgabe könnten wir aber auch lösen, in dem wir das Prinzip der Rekursion anwenden.

Bedenken wir dazu unsere 3 Regeln:

1. Es gibt einen Teil-Lösungsschritt, den wir lösen können (Subtrahiere 1 von der Zahl)
2. Dieser Schritt bringt uns der Lösung zumindest ein kleines Stück näher (wir kommen 0 näher)
3. Wir wissen, wann wir aufhören sollen (wenn wir 0 erreichen)

Eine rekursive Lösung könnte in diesem Fall z.B. dann so aussehen:

public static void main(String[] args) {
    countDown(10);
    countDownRecursion(10);
}

public static void countDown(int x) {
    for (int i = x; i >= 0; i--) {
        System.out.println(i);
    }
}

public static void countDownRecursion(int x) {
    System.out.println(x);
    if (x > 0)
        countDownRecursion(x - 1);
}

Beide Varianten geben uns das gleiche Ergebnis:

10
9
8
7
6
5
4
3
2
1
0
10
9
8
7
6
5
4
3
2
1
0

In diesem Fall ist die rekursive Lösung nicht kürzer oder länger als die „normale“ Lösung – man kann sich also aussuchen, welche man lieber mag.

Es gibt Fälle, da ist eine „normale“ Lösung kürzer/effizienter als eine rekursive, und es gibt andere, da ist die rekursive besser. Manchmal ist eine rekursive auch einfach leichter nachzuvollziehen.

2. Ein weiteres klassisches Beispiel für eine Rekursion: n!

Es gibt in der Mathematik die Kombinatorik, wo es z.B. darum geht, alle Kombinationsmöglichkeiten von verschiedenen Zahlen, Farben etc. auszurechnen. Dabei gibt es die Schreibweise n!, was in Zahlen z.B. 3! oder 5! geschrieben wird. Die Rechnung dahinter ist dabei die Folgende:

3! = 3*2*1 = 6

5! = 5*4*3*2*1 = 120

Man rechnet also ausgehend von der ersten Zahl vor dem Rufzeichen immer 1 weg und multipliziert das mit dem bisherigen Wert, bis man 1 erreicht, dann hört man auf.

Mit Hilfe einer Rekursion würde das dann so aussehen:

public static void main(String[] args) {
    System.out.println(combinator(5));
}

public static int combinator(int n) {
    if (n > 1)
        return n * combinator(n - 1);
    else return n;
}

Die Methode combinator() sieht sich dabei an, welche Zahl aktuell in n zu finden ist:

• Ist n > 1, dann berechne n * dem Ergebnis von (n – 1)
• Ist n == 1, dann gib n zurück

Die Methode macht dann für combinator(5) beispielsweise eben 5*4*3*2*1, und gibt 120 als Ergebnis zurück.

3. Die Vorteile der Rekursion

Dadurch, dass die Variablen der Parameter immer neu kopiert werden, kann ein großes Problem in viele kleine Teil-Probleme aufgeteilt werden, die so gelöst werden können, als hätten sie nichts miteinander zu tun.

Stell dir z.B. ein Dateisystem vor, das z.B. folgendermaßen aufgebaut ist:

– Ordner 1
– Ordner 2
— Datei 2_2
— Datei 2_2
– Ordner 3
— Datei 3_1
— Ordner 3_2
—Datei 3_2_1

In der obersten Ebene (z.B. C:\\) haben wir dabei genau 3 Elemente:

– Ornder 1
– Ordner 2
– Ordner 3

Wenn wir z.B. nur diese 3 Elemente anzeigen wollen, können wir das einfach über eine Schleife lösen.

Das Problem ist, dass ja in jedem dieser Ordner wieder Dateien stecken könnten, oder vielleicht noch weitere Ordner, die wieder Dateien oder Ordner in sich haben. Dies mit Schleifen zu lösen, wird rasch recht kompliziert.

Wenn wir das Ganze stattdessen mit Schleifen angehen, wird die Lösung sehr viel einfacher: Wir müssen immer nur eine einzige Ebene betrachten. In dieser schauen wir, welche Elemente hier zu finden sind, und geben sie aus. Kommt ein Ordner vor, rufen wir unsere Methode einfach erneut auf, um auch die „Kinder“ des Ordners anzuziegen. Hat dieser wieder Ordner als Kinder, gehen wir eben noch eine Stufe tiefer – aber die Rekursion macht die ganze Arbeit für uns:

public static void main(String[] args) {
    printFileStructure(0, 0);
}

public static void printFileStructure(int parentId, int depth) {

    ArrayList elements = getFilesAndFoldersByParentId(parentId); // finde alle Elemente auf dieser Ebene
    for (int i = 0; i < elements.size(); i++) { // gehe durch alle Elemente dieser Ebene
        System.out.println("-".repeat(depth) + elements.get(i).getName()); // Zeige Element an, je tiefer, desto mehr ---
        if (elements.get(i).isFolder()) // wenn Ordner
            printFileStructure(elements.get(i).getId(), depth + 1); // dann zeige auch Kinder-Elemente an
    }
}

Der obige Code einige Methoden, die man noch dazu programmieren müsste:

• getFilesAndFoldersByParentId() – gibt eine Liste der Kinder des Eltern-Elements zurück
• getName() – gibt den Namen einer Datei als String zurück
• isFolder() – findet heraus, ob ein Element ein Ordner ist (true/false)

Der Code ist sehr kurz für das, was er kann.

Ganz allgemein lässt sich sagen, dass Rekursionen meistens dann eine gute Wahl sind, wenn die Lösung eines Problems sich „verzweigt“ wie die Wurzeln eines Baumes.

4. Die Nachteile der Rekursion

Ein jeder Methoden-Aufruf braucht etwas Zeit und Speicherplatz. Ruft sich eine Methode z.B. 10x auf, ist das egal. Geht es um 1.000.000x, schafft das möglicherweise Probleme oder braucht viel länger als eine Lösung ohne Rekursion.

Das erste Beispiel in diesem Tutorial mit dem Runterzählen von einer Zahl ist beispielsweise mit Schleifen besser gelöst, weil der Overhead-Aufwand für das Aufrufen der vielen Rekursionen wegfällt.

Außerdem gibt es bei Rekursionen wie bei Schleifen auch die Gefahr einer „Endlos-Rekursion“. Die passiert immer dann, wenn die End-Bedingung, die die Rekursion aufhebt, nie erreicht wird.

Ganz allgemein sind Rekursionen aber oft ein Mittel, schwierige Probleme auf sehr elegante Art zu lösen, und gehören in den Werkzeugkoffer aller ProgrammiererInnen.

Diskussion zum Tutorial