Rekursion - Programmieren Spielend Gelernt mit dem Java-Hamster-Modell - page 331

void rechtsUm() {
linksUm();
kehrt();
}
void kehrt() {
linksUm();
linksUm();
}
Das Programm arbeitet nach dem folgenden Prinzip: Der Hamster durchsucht den vor ihm liegenden
Gang nach Körnern und kehrt zurück, falls er entweder ein Korn gefunden oder eine Wand erreicht
hat. Falls er jedoch bei seinem Weg nach vorne an eine Abzweigung oder Kreuzung gerät, dreht
er sich in die entsprechenden Richtungen um und versucht zunächst, in diesen Gängen das Korn
zu finden. 2 Dabei kann er natürlich auf weitere Abzweigungen treffen und muss in diesen Fällen
ebenfalls wieder die abzweigenden Gänge untersuchen. Sobald er ein Korn gefunden hat, braucht er
natürlich keine weiteren Gänge mehr durchsuchen und kehrt direkt zum Ausgangspunkt zurück.
17.8 Beispielprogramme
Wie Sie in den vorangegangenen Abschnitten gesehen haben, ist es im Allgemeinen nicht beson-
ders schwierig zu beweisen, dass eine rekursive Funktion korrekt ist. Für Programmieranfänger ist
es meistens viel schwieriger, für ein gegebenes Problem eine korrekte rekursive Lösung zu finden.
Leider gibt es kein allgemeingültiges Konstruktionsprinzip für rekursive Programme. Hierzu sind
Intelligenz, Intuition und vor allem Erfahrung notwendig. Um diese Erfahrung zu sammeln, schau-
en Sie sich bitte die folgenden Beispielprogramme sorgfältig an und bearbeiten Sie intensiv die
Übungsaufgaben im nächsten Abschnitt.
17.8.1 Beispielprogramm 1
In diesem Beispielprogramm wird Aufgabe 2 aus Kapitel 12.8.2 mit Hilfe des Backtracking-Verfah-
rens gelöst.
Aufgabe:
Der Hamster steht in einem durch Mauern abgeschlossenen Raum unbekannter Größe. Er hat eine
Körnerspur entdeckt (nicht unbedingt den Anfang!), die sich durch sein Territorium zieht. Die Spur
kann verzweigen. Es gibt allerdings keine „Rundwege“. Außerdem kann vorausgesetzt werden, dass
zwischen zwei Reihen der Körnerspur immer eine Reihe frei ist und dass sich außer den Körnern
der Spur keine weiteren Körner im Territorium befinden. Der Hamster soll alle Körner fressen und
zum Ausgangspunkt zurücklaufen. Abbildung 17.3 skizziert eine typische Ausgangssituation.
Lösungsidee: Der gewählte Algorithmus ist dem Algorithmus aus Abschnitt 17.7 sehr ähnlich. Die
dortigen Labyrinthgänge werden hier durch eine Körnerspur ersetzt.
2 Aus diesem Grund ist das Backtracking-Verfahren auch unter dem Namen Try-And-Error-Verfahren bekannt.