Rekursion

---

Der Hamster möchte einen Körnerhaufen ins nächste Feld schieben (englisch: move). Die folgende Prozedur sammelt alle Körner in einem Feld und legt sie im nächsten Feld ab:

void move() {
    int anzahl = 0;
    while (kornDa()) {
        nimm();
        anzahl++;
    }
    vor();

    while (anzahl > 0) {
        gib();
        anzahl–;

    }
}

 

Statt Wiederholungen kann man auch Rekursionen verwenden, die bei manchen Problemstellungen leichter zu lesen sind. Rekursion bedeutet, dass sich eine Prozedur oder Funktion selbst aufruft.

void moveRek() {
    if (kornDa()) {
        nimm();
        moveRek();

        gib();
    } else {
        vor();
    }
    // Prozedur-Ende
}

Was geschieht hier? Wir wissen bereits, dass bei Prozeduraufrufen deren Anweisungen abgearbeitet werden. Danach wird der nächste Befehl nach dem Prozeduraufruf ausgeführt. Prozeduren, die andere aufrufen, leben quasi im Hintergrund weiter.
Solange Körner da sind, ruft sich die Prozedur selbst wieder auf, sobald keine Körner mehr da sind, wird der else-Zweig ausgeführt. Hier gibt es keinen weiteren rekursiven Aufruf mehr. Alle bisher aufgerufenen Prozeduren werden nun in umgekehrter Reihenfolge nacheinander beendet. In unserem Beispiel sieht dies so aus:

Die Anweisungen im if-Zweig vor und nach dem rekursiven Aufruf von moveRek() werden gleich oft ausgeführt, wir können also auf die Variable „anzahl“ verzichten.

Rekursive Funktionen mit Rückgabewert

Die folgende Funktion zählt die Anzahl der Körner in einem Feld, ohne diese Anzahl zu verändern. Die lokale Variable „anzahl“ wird für jeden (rekursiven) Aufruf der Funktion neu angelegt und lebt innerhalb des jeweiligen if-Blocks der jeweiligen Funktion, bis dieser beendet wird.

int anzahlRek() {
    if (kornDa()) {
        nimm();
        int anzahl = anzahlRek();
        gib(); // Anzahl Koerner nicht veraendern
        return anzahl + 1;
    } else {
        return 0;
    }
}

Soll gezählt werden, wieviele Körner der Hamster nimmt, kann auf die Variable „anzahl“ verzichtet werden:

int anzahlRek() {
    if (kornDa()) {
        nimm();
        return anzahlRek() + 1;
    } else {
        return 0;
    }
}

Rekursive Funktionen mit Parametern

Rekursive Funktionen nutzen oft Parameter, die beim rekursiven Aufruf verändert werden und in der if-Bedingung getestet werden.

void  frissMax(int anzahl) {
    if ((anzahl > 0) && kornDa()) {
        nimm();
        frissMax(anzahl – 1);
    }
}

 

Sind genügend Körner vorhanden, sieht der Ablauf so aus:

Backtracking mit Rekursion

Die Suche eines Weges durch ein Labyrinth geschieht oft durch „Versuch und Irrtum“. Ein Weg wird ausprobiert, falls dieser in einer Sackgasse endet, muss man zurückgehen und die nächste Variante testen. Solche Lösungsverfahren, bei denen man manchmal Schritte rückgängig gemacht werden müssen, nennt man Backtrackingverfahren. Solche Verfahren werden meist mit Rekursion gelöst.

---