Mutable State und Undo

Häufig mutiert man ein gemeinsames Board-Array: setze Feld, rekursiver Aufruf, Feld zurücksetzen. Alternative: unveränderliche Kopien (teurer).

Fehlerquelle: Undo vergessen, dann kontaminiert der nächste Ast.

Wo gebraucht

In-place Backtracking spart Allokationen; Undo muss exakt sein. Gleiches Muster in Editoren (Command-Stack) und in Transaktionen mit Rollback.

Vertiefung

Veränderlicher Zustand vermeidet das Kopieren grosser Teilkandidaten. Eine Rekursionsebene führt eine kleine Änderung aus, ruft den nächsten Schritt auf und macht genau diese Änderung danach rückgängig. Dieses Muster ist effizient, verlangt aber eine streng symmetrische Behandlung von Vorwärts- und Rückwärtsoperation.

Die Undo-Operation muss auch dann erfolgen, wenn der rekursive Aufruf keine Lösung findet oder mehrere Lösungen sammelt. Eine alternative Strategie erzeugt pro Zweig eine neue unveränderliche Struktur. Sie ist oft leichter zu prüfen, benötigt jedoch mehr Allokationen und Kopierarbeit.

Schwierigkeitsstufen

1. Zu jeder Mutation die passende inverse Operation angeben.
2. Mehrere gekoppelte Strukturen konsistent aktualisieren und zurücksetzen.
3. Zwischen Kopieren und Undo anhand von Grösse und Fehlerrisiko abwägen.

Fallstricke

Ein frühes return kann das Undo überspringen. Ebenso problematisch sind flache Kopien verschachtelter Listen, weil innere Objekte weiterhin gemeinsam genutzt werden und Änderungen in andere Zweige durchsickern.