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

17.2.3 Rekursionstiefe

Die Rekursionstiefe einer Funktion ist definiert als die Anzahl der gleichzeitig existierenden Inkar-
nationen einer Funktion minus 1.
Rekursionstiefe 0 bedeutet somit, dass der aktuelle Aufruf einer Funktion nicht während der Aus-
führung der gleichen Funktion erfolgt ist. Dies ist bei der Ausführung der obigen Prozedur hin-
UndZurueckR der Fall, wenn sich der Hamster beim Start des Programms direkt vor einer Mauer
befindet. Befindet sich der Hamster beim Aufruf des Programms jedoch bspw. drei Felder vor einer
Mauer, so erreicht die Prozedur hinUndZurueckR eine Rekursionstiefe von 2.

17.3 Veranschaulichung des Rekursionsprinzips

In diesem Abschnitt wird das Rekursionsprinzip zunächst anhand zweier Beispiele veranschaulicht.
Außerdem wird eine Korrelation zwischen einem bestimmten Typ von iterativen Prozeduren und
rekursiven Prozeduren herausgearbeitet. Schließlich wird noch das Problem der Endlosrekursion
diskutiert.

17.3.1 Prozedur hinUndZurueckR

Schauen wir uns nun einmal genauer an, was passiert, wenn die Prozedur hinUndZurueckR aufge-
rufen wird. Abbildung 17.1 enthält mehrere mögliche Ausgangssituationen.

void hinUndZurueckR() {
if (vornFrei()) {
vor();
hinUndZurueckR(); // rekursiver Aufruf

vor();
} else {
linksUm();
linksUm();

}

}

void main() {
hinUndZurueckR();

}

(a) (b) (c)

Abbildung 17.1: Rekursionsbeispiel

Zunächst betrachten wird den Fall, dass der Hamster anfangs bereits vor einer Mauer steht (Abbil-
dung 17.1 (a)). In diesem Fall wird direkt der else-Teil der Funktion aufgerufen, der Hamster dreht
sich also um, und das Programm ist korrekt beendet.