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

Etwas komplexer ist die Situation, wenn der Hamster zwei Felder vor einer Mauer steht. In diesem
Fall hüpft der Hamster zunächst ein Feld nach vorne und befindet sich damit in der oben bereits
gelösten einfachsten Situation. Der Aufruf des Algorithmus für diese Situation führt - wie wir gerade
gesehen haben - dazu, dass sich der Hamster umdreht. Anschließend muss er nur noch ein Feld nach
vorne laufen und das Problem ist korrekt gelöst.
Noch ein wenig komplexer wird die Situation, wenn der Hamster drei Felder vor einer Mauer steht.
Er läuft ein Feld nach vorne und befindet sich wieder in einer Situation, die der Algorithmus - wie
eben gezeigt - korrekt löst. Also startet er den Algorithmus und braucht nach dessen Beendigung
nur noch ein Feld nach vorne zu laufen, um auch in diesem Fall korrekt zu arbeiten.
Man kann sogar mathematisch beweisen, dass die Prozedur hinUndZurueckR für alle Fälle korrekt
arbeitet. Hierzu bedienen wir uns des Beweisverfahrens der Vollständigen Induktion . Dieses Beweis-
verfahren funktioniert folgendermaßen: Sei n eine Natürliche Zahl. Man muss zunächst zeigen, dass
ein Algorithmus für den Fall n = 0 korrekt ist. Anschließend muss man zeigen, dass der Algorithmus
- unter der Voraussetzung, dass er für den Fall n - 1 korrekt ist - auch für den Fall n korrekt ist. Dann
gilt: Der Algorithmus ist für alle Natürlichen Zahlen korrekt.
n ist in unserem Beispiel der Abstand des Hamsters von einer Mauer. Der Fall n = 0 bedeutet also,
dass der Hamster direkt vor der Mauer steht. Wir haben oben gesehen, dass der Hamster in diesem
Fall das obige Problem korrekt löst, der Hamster dreht sich lediglich um. Nehmen wir nun an, dass
die Prozedur für den Fall n - 1 korrekt ist, d.h. steht der Hamster anfangs n - 1 Felder vor einer
Mauer, dann steht er nach Beendigung der Prozedur wieder auf seinem Ausgangsfeld, allerdings in
umgekehrter Blickrichtung. Damit ist auf sehr einfache Art und Weise zu zeigen, dass die Prozedur
auch für den Fall korrekt ist, dass der Hamster n Felder vor einer Mauer steht. In diesem Fall springt
er ja zunächst ein Feld nach vorne und befindet sich damit in der Situation n - 1, in der die Prozedur,
wie vorausgesetzt, korrekt arbeitet. Also ruft er sie auf und muss anschließend nur noch ein Feld
nach vorne springen, um auch den Fall n korrekt zu lösen. Damit gilt: Die Prozedur ist für alle
möglichen Situationen korrekt.
17.3.2 Prozedur sammleR
Bisher haben wir die Prozedur sammle immer iterativ implementiert:
void sammle() {
while (kornDa()) {
nimm();
}
}
Eine äquivalente Lösung stellt die rekursive Prozedur sammleR dar:
void sammleR() {
if (kornDa()) {
nimm();
sammleR();
}
}