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

Durch das Beweisverfahren der Vollständigen Induktion können wir auch hier wieder beweisen, dass
die Prozedur korrekt arbeitet. Der Fall n = 0 ist der, dass kein Korn auf dem Feld liegt, auf dem sich
der Hamster beim Aufruf der Prozedur befindet. In diesem Fall liefert der boolesche Ausdruck der
if-Bedingung den Wert false , und die Prozedur ist mit dem korrekten Ergebnis beendet.
Nehmen wir nun an, die Prozedur ist korrekt für den Fall n - 1, d.h. dass auf dem aktuellen Feld n -1
Körner liegen, und betrachten wir den Fall, dass sich auf dem aktuellen Feld n Körner befinden. Wird
die Prozedur in dieser Situation aufgerufen, dann frisst der Hamster zunächst ein Korn. D.h. aber,
dass sich nun nur noch n - 1 Körner auf dem aktuellen Feld befinden. Wie vorausgesetzt, arbeitet
die Prozedur aber in diesem Fall korrekt, sodass der anschließende Aufruf der Funktion dafür sorgt,
dass die Prozedur auch für den Fall n korrekt funktioniert. Also ist - laut Vollständiger Induktion -
die Prozedur für alle möglichen Fälle korrekt.
17.3.3 Korrelation zwischen iterativen und rekursiven Prozeduren
Schauen Sie sich die folgende Abstrahierung einer iterativen Prozedur an:
void p() {
while (<Bedingung>)
<Anweisung>
}
Hierbei sei Bedingung eine beliebige Bedingung und Anweisung eine beliebige Anweisung. Dann
ist leicht zu erkennen, dass die Prozedur p äquivalent ist zu folgender Prozedur p2 und diese ist
wiederum äquivalent zu Prozedur p3 :
void p2() {
if (<Bedingung>) {
<Anweisung>
while (<Bedingung>)
<Anweisung>
}
}
void p3() {
if (<Bedingung>) {
<Anweisung>
if (<Bedingung>) {
<Anweisung>
while (<Bedingung>)
<Anweisung>
}
}
}
Das kann man prinzipiell endlos so weiter treiben. Wenn man sich die Prozeduren genauer anschaut,
erkennt man leicht das Prinzip, das dem Verfahren zugrunde liegt: Ab der zweiten if-Anweisung
entspricht die if-Anweisung eigentlich immer einem erneuten Aufruf der Prozedur, sodass man die
Prozedur rekursiv folgendermaßen definieren kann: