Rekursion, Teile und herrsche, Rücksetzverfahren

„Um zu verstehen, was Rekursion ist, muss man zuerst verstehen, was Rekursion ist."

Der Witz trifft die Sache und verfehlt sie zugleich. Er trifft, weil sich eine rekursive Definition tatsächlich auf sich selbst beruft. Er verfehlt, weil ihm der entscheidende Teil fehlt: der Abbruch.

Ohne Abbruch wäre Rekursion ein Zirkelschluss. Mit Abbruch ist sie eines der mächtigsten Werkzeuge der Informatik, und sie löst Aufgaben, die mit Schleifen kaum formulierbar wären.

Vorausgesetzt werden Unterprogramme mit Parametern und Rückgabewerten aus Programmieren: Variablen, Kontrollstrukturen, Unterprogramme, der Stapel aus Datentypen und Datenstrukturen und die O-Notation aus Aufwand von Algorithmen.

Ein Unterprogramm heißt rekursiv, wenn es sich selbst aufruft. Damit das kein endloser Rückgriff wird, braucht es zwingend zwei Teile:

Basisfall. Ein Fall, der ohne weiteren Aufruf beantwortet wird. Er ist der Boden. Rekursionsschritt. Der Aufruf auf ein kleineres Teilproblem, das dem Basisfall näher liegt.

Beide sind unverzichtbar. Fehlt der Basisfall, läuft die Rekursion endlos. Führt der Rekursionsschritt nicht näher an den Basisfall heran, ebenfalls.

Beispiel Fakultät. Die mathematische Definition ist bereits rekursiv:

fakultaet(n):
    wenn n = 0:
        gib 1 zurück              // Basisfall
    sonst:
        gib n * fakultaet(n-1)    // Rekursionsschritt

Die Umsetzung ist eine wörtliche Übersetzung der Definition, und genau das ist die Stärke der Rekursion: Wo ein Problem rekursiv definiert ist, ist die rekursive Lösung die natürliche.

Bei jedem Aufruf legt der Rechner einen Eintrag auf den Aufrufstapel mit den lokalen Werten und der Stelle, an der es nach der Rückkehr weitergeht. Für $\texttt{fakultaet(4)}$:

fakultaet(4)  →  4 * fakultaet(3)         ↓ hinein
fakultaet(3)  →  3 * fakultaet(2)         ↓
fakultaet(2)  →  2 * fakultaet(1)         ↓
fakultaet(1)  →  1 * fakultaet(0)         ↓
fakultaet(0)  →  1                        ← Boden erreicht

fakultaet(1)  =  1 * 1  = 1               ↑ heraus
fakultaet(2)  =  2 * 1  = 2               ↑
fakultaet(3)  =  3 * 2  = 6               ↑
fakultaet(4)  =  4 * 6  = 24              ↑

🔴 Zwei Beobachtungen, die den größten Teil aller Missverständnisse ausräumen:

Erst geht es hinein, dann heraus. Die Multiplikationen finden nach dem tiefsten Aufruf statt, auf dem Rückweg. Wer glaubt, die Rechnung geschehe beim Hineingehen, kommt bei jeder Nachverfolgung durcheinander.

Der Stapel wächst mit der Tiefe. Jeder offene Aufruf belegt Speicher. Bei $\texttt{fakultaet(100000)}$ läuft der Aufrufstapel über, und das Programm bricht ab. Rekursionstiefe ist also nicht kostenlos, und das ist der wichtigste praktische Nachteil.

Die Fakultät ist ein schlechtes Beispiel für den Nutzen der Rekursion, auch wenn sie ein gutes für ihr Prinzip ist. Eine Schleife leistet dasselbe, ist schneller und braucht keinen Stapelplatz.

Die Frage lautet deshalb: Wann lohnt sich Rekursion?

Wenn sich das Problem natürlich in gleichartige kleinere Teilprobleme zerlegt.

Typische Fälle:

• Bäume und Verzeichnisse. Ein Ordner enthält Ordner, die Ordner enthalten. Eine Schleife müsste die Schachtelungstiefe kennen, die Rekursion nicht.
• Teile und herrsche. Sortieren durch Mischen, binäre Suche.
• Alle Möglichkeiten durchprobieren. Labyrinth, Damenproblem, Sudoku.

In all diesen Fällen ist die rekursive Fassung kürzer und verständlicher. Bei einfachen Wiederholungen dagegen ist die Schleife die bessere Wahl.

Die Türme von Hanoi: Ein Stapel von $n$ Scheiben soll von Stab A nach C, es darf nur eine Scheibe auf einmal bewegt werden, und nie eine größere auf eine kleinere.

Die rekursive Lösung besteht aus drei Zeilen:

bewege(n, von, nach, hilf):
    wenn n = 0: fertig                        // Basisfall
    bewege(n-1, von, hilf, nach)              // oberste n-1 auf den Hilfsstab
    verschiebe die unterste Scheibe von → nach
    bewege(n-1, hilf, nach, von)              // die n-1 wieder obendrauf

Der Gedanke dahinter ist bemerkenswert: Man löst das Problem, ohne es ganz zu durchdenken. Man nimmt an, dass der Fall $n-1$ bereits gelöst ist, und beschreibt nur, wie man daraus den Fall $n$ gewinnt. Genau das ist die Denkweise der vollständigen Induktion.

Die Zahl der Züge ist $2^n - 1$. Bei 64 Scheiben, wie in der Legende, wären das über $1{,}8 \cdot 10^{19}$ Züge; bei einem Zug pro Sekunde dauerte das länger als das bisherige Alter des Universums. Die Lösung ist also kurz und trotzdem exponentiell teuer.

Die Fibonacci-Folge lädt zur direkten Umsetzung ein:

fib(n):
    wenn n ≤ 1: gib n zurück
    gib fib(n-1) + fib(n-2)

Kurz, richtig und katastrophal langsam. Der Grund ist die Mehrfachberechnung:

                fib(5)
              /        \
         fib(4)        fib(3)
         /    \        /    \
    fib(3)  fib(2) fib(2)  fib(1)
    /    \
fib(2)  fib(1)

$\texttt{fib(3)}$ wird zweimal berechnet, $\texttt{fib(2)}$ dreimal, und bei größerem $n$ wächst das exponentiell. Für $\texttt{fib(50)}$ wären es über $10^{10}$ Aufrufe.

Abhilfe: Zwischenergebnisse merken statt neu berechnen. Man nennt das Speichern bereits berechneter Werte, und damit sinkt der Aufwand von $O(2^n)$ auf $O(n)$. Alternativ genügt eine einfache Schleife, die von unten hochrechnet.

🔴 Die Lehre daraus ist wichtig: Rekursiv formulierbar heißt nicht rekursiv sinnvoll. Prüfe immer, ob dieselben Teilprobleme mehrfach auftreten.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Manche Aufgaben lassen sich nur durch Ausprobieren lösen, aber nicht durch blindes: Ein Labyrinth, ein Sudoku, die Frage, ob acht Damen auf ein Schachbrett passen, ohne sich zu bedrohen.

Das Rücksetzverfahren (Backtracking) geht so vor:

Wähle eine mögliche Fortsetzung. Prüfe, ob sie die Bedingungen noch erfüllen kann. Vertiefe rekursiv, wenn ja. Setze zurück und probiere die nächste Möglichkeit, wenn nein.

loese(teilloesung):
    wenn teilloesung vollständig:
        gib sie aus, fertig
    für jede mögliche Fortsetzung:
        wenn Fortsetzung zulässig:
            füge sie hinzu
            loese(teilloesung)          // vertiefen
            entferne sie wieder         // zurücksetzen

Die Zeile „entferne sie wieder" ist der Kern und der Namensgeber. Sie stellt den Zustand vor dem Versuch wieder her, damit die nächste Möglichkeit auf sauberem Grund beginnt.

Beim Damenproblem setzt man Zeile für Zeile eine Dame. Steht sie schlecht, geht man in die vorige Zeile zurück und versucht dort die nächste Spalte.

Der entscheidende Gewinn liegt im frühen Abschneiden. Erkennt man in Zeile 3, dass keine Fortsetzung mehr möglich ist, spart man sich alle Anordnungen der übrigen Zeilen auf einen Schlag. Beim Acht-Damen-Problem gäbe es $8^8 \approx 16{,}8$ Millionen Stellungen; das Rücksetzverfahren prüft nur einen kleinen Bruchteil davon.

Wichtig ist aber, was das nicht bedeutet: Der Aufwand bleibt im schlechtesten Fall exponentiell. Das Rücksetzverfahren macht ein schweres Problem nicht leicht, es macht es nur oft handhabbar. Damit steht es genau an der Grenze, die im Kapitel über $P$ und $NP$ beschrieben wurde.