Backtracking (Prinzip 2 )

	Das Backtracking-Prinzip lässt sich elegant als rekursiver Algorithmus formulieren und dann auch so implementieren.
Definition	Ein rekursiver Algorithmus ist ein Algorithmus, der sich selbst wieder aufruft.
Backtracking rekursiv	EF bezeichnet eine Entscheidungsfolge. Algorithmus BacktrackingRek (EF) falls EF Lösung ist      stop sonst      für alle jetzt möglichen Entscheidungen           falls Entscheidung nicht erkennbar falsch                verlängere Entscheidungsfolge EF um diese Entscheidung,                     (die verlängerte Entscheidungsfolge heiße EF')                BacktrackingRek(EF')
	Der Algorithmus wird mit der leeren Entscheidungsfolge gestartet.
der Rechner spinnt den Ariadnefaden!	Bei Verwendung von Rekursion muss man sich keine Gedanken mehr darüber machen, wie man eine Entscheidung zurücknimmt: der Rechner organisiert dies von sich aus beim Verwalten der rekursiven Aufrufe.
mehr zum Stack im Modul Lineare Datenstrukturen	Der Rechner verwaltet eine Datenstruktur Stack ('Stapel'). Bei jedem rekursiven Aufruf werden die aktuellen Parameter auf den Stapel gelegt ('gemerkt'). Nach Rückkehr ('return') von einem rekursiven Aufruf werden die dann aktuellen Parameter wieder vom Stack eingelesen.
	Beobachte, wie die rekursive Version des Algorithmus Zum Ausgang für ein kleines Labyrinth abläuft. Die Parameter EF, M und X werden jeweils im Stack verwaltet.

Seite 5/10