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

int bisZurMauer() {
int schritte = 0;
while (vornFrei()) {
vor();
schritte++;

}
return schritte;

}

Eine äquivalente rekursive Funktion hat folgende Gestalt:

int bisZurMauerR() {
if (vornFrei()) {
vor();
return (bisZurMauerR() + 1);
} else {
return 0;

}

}

Auch in diesem Beispiel wird wieder vom Prinzip der Komplexitätsreduktion Gebrauch gemacht.
Die einfachste Situation ist dadurch gekennzeichnet, dass der Hamster bereits vor einer Mauer steht;
es wird der Wert 0 zurückgeliefert. In den anderen Fällen reduziert der Hamster die Komplexität der
Situation zunächst durch Ausführung des vor(); -Befehls um 1 . Anschließend ruft er rekursiv die
Funktion bisZurMauerR auf. Diese liefert (irgendwann) den Wert für die um den Wert 1 reduzierte
Situation. Dieser Wert wird nun dementsprechend um den Wert 1 erhöht und als Funktionswert
geliefert.
Die folgende Skizze verdeutlicht den Aufruf der Funktion bisZurMauerR in einer Situation, in der
der Hamster 3 Felder vor einer Mauer steht, also 2 Schritte bis zur Mauer zu laufen hat:

main bisZurMauerR (1.) bisZurMauerR (2.) bisZurMauerR (3.)

bisZurMauer --> vornFrei -> true
vor
bisZurMauerR --> vornFrei -> true

vor
bisZurMauerR

--> vornFrei -> false
return 0

0
<--

return 0 + 1

1
<--

return 1 + 1

2
<--

In der Tat liefert die Funktion den korrekten Wert 2 für diese Situation zurück.

17.5 Rekursive Funktionen mit lokalen Variablen

Im folgenden Beispiel wird ein weiterer Aspekt rekursiver Funktionen erläutert. Was passiert eigent-
lich, wenn eine rekursive Funktion lokale Variablen besitzt? Die Funktion anzahlKoernerR liefert