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

while (vornFrei()) {
vor();
schritte++;
}
// kehrt
linksUm();
linksUm();
// laufe zurueck
while (schritte > 0) {
vor();
schritte--;
}
}
void main() {
hinUndZurueck();
}
Die Prozedur hinUndZurueck realisiert also eine iterative Lösung des gegebenen Problems. Eine
äquivalente rekursive Lösung bietet folgende rekursiv definierte Prozedur hinUndZurueckR :
void hinUndZurueckR() {
if (vornFrei()) {
vor();
hinUndZurueckR();
vor();
} else {
linksUm();
linksUm();
}
}
void main() {
hinUndZurueckR();
}
Was unterscheidet die beiden Prozeduren hinUndZurueck und hinUndZurueckR ? Zunächst ein-
mal fällt auf, dass in der Prozedur hinUndZurueckR weder eine while-Schleife noch eine Variable
eingesetzt wird. Das Wesentliche ist jedoch, dass in der Prozedur hinUndZurueckR eine Prozedur
aufgerufen wird, nämlich hinUndZurueckR selbst. Genau dieses Phänomen, dass während der Aus-
führung einer Funktion die gleiche Funktion ein weiteres Mal aufgerufen wird, wird als Rekursion
bezeichnet.
17.2 Definitionen
Bevor wir den Begriff der „Rekursion“ exakt definieren können, muss zuvor ein weiterer Begriff
eingeführt werden, nämlich der Begriff der „Inkarnation“.