Rekursion mit Entscheidung

Muster: for jede Option: if zulässig: anwenden; if solve(): return true; rückgängig; return false.

Basisfall: alle Positionen gesetzt oder Ziel erreicht.

Wo gebraucht

Entscheidungstiefe = Anzahl der Variablen. Framework für kombinatorische Suche, bevor man zu Heuristiken oder DP wechselt.

Vertiefung

Eine Entscheidungsrekursion beantwortet an jeder Position eine kleine Frage, etwa ob ein Element aufgenommen wird. Der Basisfall bewertet den vollständig oder ausreichend bearbeiteten Zustand. Damit die Rekursion terminiert, muss jeder Aufruf ein wohldefiniertes Mass verkleinern, typischerweise die Zahl noch unbehandelter Elemente.

Existenzprobleme können kurzschliessen: Sobald ein Zweig erfolgreich ist, müssen weitere Alternativen nicht untersucht werden. Beim Zählen oder Auflisten gilt das nicht. Dann werden die Resultate aller zulässigen Kinder zusammengeführt, wodurch auch der Rückgabetyp die Suchsemantik ausdrückt.

Schwierigkeitsstufen

1. Basisfall und Fortschrittsmass einer binären Entscheidung formulieren.
2. Existenzsuche, Zählen und Auflisten in getrennte Rückgaben übersetzen.
3. Memoisierung einsetzen, wenn verschiedene Pfade denselben Restzustand erreichen.

Fallstricke

Ein Basisfall kann zu früh Erfolg melden, obwohl noch Nebenbedingungen offen sind. Auch darf ein fehlgeschlagener erster Zweig nicht automatisch das Gesamtergebnis bestimmen, solange eine zweite Alternative existiert.