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

void pR() {
if (<Bedingung>) {
<Anweisung>
pR();
}
}
Dabei gilt: Die rekursive Prozedur pR ist semantisch äquivalent zur iterativen Prozedur p .
17.3.4 Endlosrekursion
In Kapitel 10.2.7 haben wir erfahren, was sogenannte Endlosschleifen sind, nämlich Wiederholungs-
anweisungen, die nie beendet werden. Ein ähnliches Phänomen kann auch in rekursiven Prozeduren
auftreten. Man bezeichnet es als Endlosrekursion . Schauen Sie sich dazu die folgende Prozedur
sammleR2 an, bei der gegenüber der Prozedur sammleR zwei Anweisungen vertauscht werden:
void sammleR() {
if (kornDa()) {
nimm();
sammleR();
}
}
void sammleR2() {
if (kornDa()) {
sammleR2();
nimm();
}
}
Ein Aufruf der Funktion sammleR2 in einer Situation, dass der Hamster auf einem Feld mit Körnern
steht, führt zu einer Endlosrekursion. Die Prozedur sammleR2 ruft sich nämlich immer wieder selbst
auf, ohne dass die Komplexität der Situation vorher durch das Fressen eines Korns reduziert wird.
Programme mit Endlosrekursionen sind, wie Programme mit Endlosschleifen, im Allgemeinen feh-
lerhaft. Es gibt jedoch einen Unterschied: Während Programme mit Endlosschleifen niemals enden,
werden Programme mit Endlosrekursion normalerweise irgendwann mit einem Laufzeitfehler abge-
brochen. Der Grund hierfür liegt darin, dass das Laufzeitsystem (Kapitel 3.2) im Allgemeinen bei
jeder Erzeugung einer neuen Inkarnation einer Funktion Speicherplatz auf dem Stack (siehe Kapitel
4.4.3) anlegt. Irgendwann ist dann der Stack voll, d.h. kein Speicherplatz mehr verfügbar, sodass das
Laufzeitsystem das Programm mit einem Fehler beenden muss.
17.4 Rekursive Funktionen
Bisher haben wir in den Beispielen dieses Kapitels lediglich rekursive Prozeduren kennengelernt.
Aber natürlich können auch Funktionen rekursiv definiert werden. Die folgende iterative Funktion
lässt den Hamster bis zur nächsten Wand laufen und liefert die Anzahl an benötigten Schritten: