jario_
Zur Übersicht

Algorithmen und Datenstrukturen · Kapitel 6

Rekursion und Backtracking

Rekursion kennst du schon aus den Grundlagen: Eine Methode ruft sich selbst auf. In diesem Kapitel siehst du, was dabei im Speicher passiert, wann Rekursion besser passt als eine Schleife und wie man mit Backtracking systematisch alle Möglichkeiten durchprobiert: Anordnungen, Teilmengen, Wege durch ein Labyrinth.

Abbruchfall und rekursiver Fall

Jede rekursive Methode hat zwei Teile:

  • Der Abbruchfall (Basisfall) ist so klein, dass das Ergebnis direkt feststeht: eine Zahl mit einer Ziffer, ein Text mit höchstens einem Zeichen, ein leeres Array.
  • Der rekursive Fall führt das Problem auf eine kleinere Version desselben Problems zurück und ruft dafür die Methode selbst auf.

Den Abbruchfall prüfst du immer zuerst. Bei Arrays wird das Problem kleiner, indem ein Index mitwandert (index + 1), bei Texten mit substring(1), bei Zahlen mit n - 1 oder n / 10.

public class Main {    public static int countDigits(int n) {        if (n < 10) {            return 1;        }        return 1 + countDigits(n / 10);    }
    public static String reverse(String s) {        if (s.length() <= 1) {            return s;        }        return reverse(s.substring(1)) + s.charAt(0);    }
    public static void main(String[] args) {        System.out.println(countDigits(7));        System.out.println(countDigits(2026));        System.out.println(reverse("stack"));    }}

Der Aufrufstapel

Jeder Methodenaufruf bekommt einen eigenen Bereich auf dem Aufrufstapel (Call Stack) mit eigenen Parametern und lokalen Variablen. Ruft sich factorial(4) selbst auf, liegen am Ende vier Aufrufe übereinander, jeder mit seinem eigenen n. Erst wenn der oberste fertig ist, macht der darunter weiter.

Daraus folgt: Was vor dem rekursiven Aufruf steht, läuft in der Reihenfolge der Aufrufe, was danach steht, in umgekehrter Reihenfolge. Das Einrücken im Beispiel zeigt, wie tief der Stapel gerade ist.

public class Main {    public static int factorial(int n, String indent) {        System.out.println(indent + "factorial(" + n + ") called");        int result;        if (n <= 1) {            result = 1;        } else {            result = n * factorial(n - 1, indent + "  ");        }        System.out.println(indent + "factorial(" + n + ") returns " + result);        return result;    }
    public static void main(String[] args) {        factorial(4, "");    }}

Der Stapel ist begrenzt. Ein paar tausend Aufrufe übereinander gehen gut, Millionen nicht: Dann bricht Java mit StackOverflowError ab.

Rekursion oder Schleife?

Alles, was eine Schleife kann, kann auch Rekursion, und umgekehrt. Beide Summen im Beispiel brauchen O(n) Schritte. Die rekursive Fassung braucht aber zusätzlich O(n) Platz auf dem Stapel, die Schleife nur eine Variable.

Faustregel:

  • Schleife, wenn du ein Array oder eine Liste einfach von vorne nach hinten durchgehst.
  • Rekursion, wenn sich das Problem natürlich in Teilprobleme gleicher Art zerlegt: Türme von Hanoi, Bäume (nächstes Kapitel), Quicksort und Mergesort, und alle Aufgaben, bei denen man Möglichkeiten durchprobiert.
public class Main {    public static int sumRecursive(int[] numbers, int index) {        if (index == numbers.length) {            return 0;        }        return numbers[index] + sumRecursive(numbers, index + 1);    }
    public static int sumLoop(int[] numbers) {        int total = 0;        for (int number : numbers) {            total += number;        }        return total;    }
    public static void main(String[] args) {        int[] numbers = {4, 8, 15, 16, 23, 42};        System.out.println(sumRecursive(numbers, 0));        System.out.println(sumLoop(numbers));    }}

Backtracking: wählen, erkunden, zurücknehmen

Backtracking baut eine Lösung Schritt für Schritt auf. An jeder Stelle gibt es mehrere Möglichkeiten. Für jede davon gilt dasselbe Muster:

  1. Wählen: eine Möglichkeit festlegen, z. B. einen Buchstaben anhängen und als benutzt markieren.
  2. Erkunden: rekursiv den nächsten Schritt lösen.
  3. Zurücknehmen: die Wahl rückgängig machen, damit die nächste Möglichkeit von einem sauberen Stand aus startet.

Ist die Lösung vollständig (alle Buchstaben gelegt, Ausgang erreicht), wird sie ausgegeben, gezählt oder gespeichert. Passt eine Teillösung nicht mehr (Dame bedroht, Wand im Weg), bricht man diesen Zweig sofort ab. Genau das macht Backtracking schneller als stures Ausprobieren aller Kombinationen.

public class Main {    static int found = 0;
    public static void permute(char[] letters, boolean[] used, StringBuilder current) {        if (current.length() == letters.length) {            System.out.println(current);            found++;            return;        }        for (int i = 0; i < letters.length; i++) {            if (used[i]) {                continue;            }            used[i] = true;                          // choose            current.append(letters[i]);            permute(letters, used, current);         // explore            current.deleteCharAt(current.length() - 1);            used[i] = false;                         // undo        }    }
    public static void main(String[] args) {        char[] letters = {'a', 'b', 'c'};        permute(letters, new boolean[letters.length], new StringBuilder());        System.out.println(found + " permutations");    }}

Laufzeit: schnell exponentiell

Rekursive Lösungen, die sich pro Aufruf zweimal selbst aufrufen, wachsen schnell. Die Türme von Hanoi brauchen für n Scheiben 2ⁿ − 1 Züge, also O(2ⁿ). Jede Scheibe mehr verdoppelt die Arbeit.

Genauso beim Backtracking: Es gibt 2ⁿ Teilmengen und n! Anordnungen von n Elementen. Für n = 20 sind das über eine Million Teilmengen und mehr als 2 Trillionen Anordnungen. Solche Algorithmen taugen nur für kleine n. Abbrechen, sobald ein Zweig nicht mehr passt, hilft viel, ändert aber oft nichts an der Größenordnung im schlimmsten Fall.

public class Main {    static long moves = 0;
    public static void move(int n, char from, char to, char via) {        if (n == 0) {            return;        }        move(n - 1, from, via, to);        moves++;        move(n - 1, via, to, from);    }
    public static void main(String[] args) {        for (int n = 1; n <= 20; n += 4) {            moves = 0;            move(n, 'A', 'C', 'B');            System.out.println(n + " disks: " + moves + " moves");        }    }}

Typische Fehler

  • Abbruchfall fehlt oder ist falsch

    Fehlt der Abbruchfall, ruft sich die Methode endlos auf, bis StackOverflowError kommt. Ebenso tückisch ist ein falscher Abbruchfall: if (n <= 1) return n; liefert für factorial(0) den Wert 0 statt 1. Prüfe den Abbruchfall mit den kleinsten Eingaben, auch 0 und dem leeren Array.

  • Das Problem wird nicht kleiner

    sumFrom(numbers, index) statt sumFrom(numbers, index + 1) ruft sich immer mit demselben Wert auf und erreicht den Abbruchfall nie. Jeder rekursive Aufruf muss näher an den Abbruchfall kommen. Bei n - 2 statt n - 1 kann er auch übersprungen werden: n == 0 trifft eine ungerade Zahl nie, n <= 0 schon.

  • Zurücknehmen vergessen

    Beim Backtracking muss jede Wahl nach dem Erkunden rückgängig gemacht werden: Buchstabe wieder entfernen, used[i] wieder auf false, Labyrinthzelle wieder auf '.'. Sonst startet die nächste Möglichkeit mit Resten der vorigen. Und wer eine Teillösung speichert, speichert eine Kopie (new ArrayList<>(current)), denn die Liste selbst wird gleich wieder verändert.