Selbstaufrufende Funktionen

Willemers Informatik-Ecke

Rekursion

Bestimmte Aufgabenstellungen lassen sich am besten dadurch lösen, dass Funktionen sich selbst aufrufen. Einen solchen Selbstaufruf nennt man Rekursion. Dabei entsteht eine Wiederholung, die über den Selbstaufruf läuft. Damit das nicht zur Endlosschleife wird, muss der Selbstaufruf unter einer Bedingung stehen, die irgendwann endet. So sind viele Schleifen auch als Rekursion programmierbar und umgekehrt. Das erste Beispiel zeigt eine solche einfache Umsetzung einer Schleife, um das Prinzip einer Rekursion darzustellen. Beide Funktionen berechnen die Summe der Zahlen von 1 bis max.

[Summe über 1 bis n (reksumme.cpp)] 

long summeRekursiv(long max)
{
    if (0 < max)
    {
        return summeRekursiv(max - 1) + max;
    }
    return 0;
}

long summeIterativ(long max)
{
    long Summe = 0;
    while (0 < max)
    {
        Summe += max;
        max--;
    }
    return Summe;
}

Die Einsparung zweier Zeilen wird Sie sicher nicht beeindrucken. Aber in dem Beispiel geht es weniger um die Frage besonderer Eleganz oder Effizienz, sondern um die Darstellung eines alternativen Ansatzes. An diesem einfachen Beispiel lässt sich eher verstehen, wie eine rekursive Funktion arbeitet. Der Rumpf der rekursiven Funktion entspricht einem Schleifenkörper. Er enthält nicht die Lösung des ganzen Problems, sondern implementiert einen Schritt. So wie bei der Schleife das Gesamtproblem erst durch die Wiederholung gelöst wird, so wird die Rekursion erst durch den Selbstaufruf zur Lösung kommen.

Hintergrund

Eine Rekursion nutzt den Stack, in dem bei jedem Funktionsaufruf die Rücksprungadresse, die lokalen Variablen und die Parameter abgelegt werden. Wenn die Funktion ohne Seiteneffekte programmiert wurde, enthält der Stack den kompletten Zustand des bisherigen Funktionsablauf. Ruft sie sich selbst mit anderen Parametern auf, wird der bisherige Zustand auf dem Stack erhalten, quasi eingefroren. Oben auf dem Stack wird für die neue Funktion wieder eine neue Umgebung geschaffen. Endet die Funktion, wird deren Umgebung vom Stack gelöscht und sie kehrt zu dem eingefrorenen Zustand wieder zurück. Das folgende Schema soll verdeutlichen, wie die Rekursion arbeitet: 

summeRekursiv(4)                                         [=6]+4
      summeRekursiv(3)                              [=3]+3
             summeRekursiv(2)                  [=1]+2
                    summeRekursiv(1)      [=0]+1
                           summeRekursiv(0)

Zunächst wird die Funktion summeRekursiv() mit dem Parameter 4 aufgerufen. Sofern dieser nicht 0 ist, ruft sie zunächst sich selbst mit einem um 1 reduzierten Parameter auf. Hier wäre das 3. So wiederholt sich Aufruf um Aufruf, bis der Parameter endlich 0 ist. Dann ruft die Funktion nicht mehr sich selbst auf, sondern läuft durch. Sie liefert 0 zurück. Sie springt in den vorigen Funktionsaufruf zurück, in dem der Parameter max noch 1 war. Dies wird zum Ergebnis des Aufrufs hinzuaddiert und als Ergebnis zurückgegeben. Die Rückkehr erfolgt in die Stufe, in der max 2 war. Und so geht es weiter, bis summeRekursiv(4) schließlich 10 zurückgibt.

Einsatzbereich

Bestimmte Aufgaben, die sich rekursiv in wenigen Zeilen lösen lassen, sind ohne Rekursion nur mit erheblichem Aufwand zu erledigen. Dazu gehören vor allem Probleme, die sich baumartig verzweigen.

include

Stellen Sie sich beispielsweise eine Funktion vor, die ein C++-Listing so drucken soll, dass alle Dateien, die per #include eingebunden werden, mitgedruckt werden. Dabei ist zu berücksichtigen, dass jede eingebundene Datei wiederum mehrere #include-Anweisungen enthalten kann. Mit Schleifen bekommen Sie das nur schwer in den Griff, da das Programm nach dem Ausdruck einer Datei an die Stelle zurückkehren muss, an der es zuletzt gewesen ist. Das folgende Skelett einer Druckfunktion zeigt, wie das Problem durch eine Rekursion zu lösen wäre.

[Druckroutine rekursiv] 

DruckeRekursiv(char * DateiName)
{
    OeffneDatei(DateiName)
    while (!EndeDerDatei())
    {
        LiesZeile();
        if (IncludeAnweisung(IncludeDateiName))
        {
             DruckeRekursiv(IncludeDateiName);
        }
        DruckeZeile();
    }
}

Diese Funktion kommt mit beliebig verschachtelten #include-Befehlen zurecht und ist insgesamt recht übersichtlich. Sie können davon ausgehen, dass der C++-Präprozessor seine Dateien ebenfalls rekursiv einlesen wird.

Beispiel: binärer Baum

Struktur eines Binärbaums

Binäre Bäume lassen sich am einfachsten per Rekursion bearbeiten. Ein binärer Baum besteht aus Knoten, die jeweils zwei Äste besitzen, die wiederum auf einen weiteren Knoten zeigen. Jeder Knoten enthält eine Information.

An dieser Stelle steht im Buch die Abbildung "Binärer Baum" (binbaum)

Es zeigt sich wieder einmal, dass es um das biologische Wissen der meisten Informatiker betrüblich aussieht: Die Wurzel des Baums ist oben. Im vorliegenden Fall liegt in der Wurzel die 27. Nach links enthalten alle Knoten kleinere, nach rechts größere Werte. Das gilt in diesem Baum für alle Knoten. Sind die Informationen wie hier sortiert angeordnet, dann können sie extrem schnell gefunden werden. Um einen Baum in einem Programm nachzubilden, muss ein Knoten beschrieben werden und die Knoten untereinander in Baumform verbunden werden. Die Datenstruktur eines Knotens hat folgendes Aussehen:

[Knoten eines Binärbaums] 

struct tBaum
{
    int Inhalt;
    tBaum * links;
    tBaum * rechts;
};

Ein Baum entsteht, wenn mehrere Knoten durch die Zeiger links oder rechts miteinander verbunden werden und dabei kein Kreis entsteht. Zur Erinnerung: Ein Knoten wird mit dem Befehl new erzeugt. Der Rückgabewert ist der Zeiger auf den neuen Knoten. Um auf die Elemente des Knotens zuzugreifen, wird an den Zeigernamen die Zeichenkombination -> gefolgt vom Elementnamen angehängt

[Knoten eines Binärbaums erzeugen und füllen] 

tBaum *NeuKnoten;
NeuKnoten = new tBaum;
NeuKnoten->Inhalt = 5;

Auslesen

Das nächste Listing zeigt eine Funktion, die einen binären Baum durchläuft und ausgibt. Vorher sollten Sie vielleicht einmal mit einem Bleistift versuchen, den Baum aus der Abbildung in geordneter Reihenfolge abzulaufen. Dabei werden Sie sich immer links halten. Wenn es nicht mehr weitergeht, zeigen Sie den Inhalt des Knotens an, versuchen es dann rechts und versuchen von dort wieder, sich möglichst links zu halten. Wenn Sie sich nun die rekursive Funktion ZeigeBaum() ansehen, werden Sie feststellen, dass sie genau in dieser Weise vorgeht. Zunächst prüft sie, ob das aktuelle Blatt überhaupt existiert. Dann ruft die Funktion sich selbst für den Zweig zur linken auf. Dadurch wird die Funktion sich immer wieder aufrufen, bis es keinen linken Zweig mehr gibt. Die Funktion, die keinen weiteren Zeiger mehr findet, wird den Inhalt des aktuellen Knotens ausgeben. Danach ruft sich die Funktion mit dem rechten Teilast auf. Von dort wird die Funktion wiederum den gesamten linken Teilast bis zum Ende durchlaufen. Sie sehen also, dass die rekursive Lösung durchaus der intuitiven Lösung entspricht. Sie werden den Vorteil des rekursiven Ansatzes sofort verstehen, wenn Sie versuchen, die Ausgabe eines solchen Baums durch eine Schleife zu implementieren.

[Ausgabe eines sortierten Binärbaums (binbaum.cpp)] 

struct tBaum
{
    int Inhalt;
    tBaum * links;
    tBaum * rechts;
};

void ZeigeBaum(tBaum *Blatt)
{
    if (Blatt==0) return;
    ZeigeBaum(Blatt->links);
    cout << Blatt->Inhalt << endl;
    ZeigeBaum(Blatt->rechts);
}

Einfügen

Entsprechend ist auch das Einfügen in den Baum am einfachsten rekursiv zu implementieren. Dabei wird zunächst das Blatt gesucht, dessen Nachfolger der neue Eintrag werden soll. Diese Stelle muss ein Null-Zeiger sein. An dieser Stelle wird ein neues Blatt eingehängt. Das ist auch gleichzeitig das Rekursionsende. Hier wird das neue Element in den Baum eingefügt und die Adresse des Blatts zurückgegeben, damit es vom Aufrufer in den Baum eingehängt wird.

[Einfügen in einen sortierten Binärbaum (binbaum.cpp)] 

tBaum * Einfuegen(tBaum *Blatt, int Inhalt)
{
    if (Blatt==0) // Freie Position gefunden
    { // Neues Blatt einfügen
        Blatt = new tBaum;
        Blatt->links = Blatt->rechts = 0;
        Blatt->Inhalt = Inhalt;
        return Blatt; // Zeiger auf neues Blatt zurückgeben
    }
    if (Inhalt < Blatt->Inhalt)
    { // Zuweisung behält altes Blatt oder das neue
        Blatt->links = Einfuegen(Blatt->links, Inhalt);
    }
    else if (Inhalt > Blatt->Inhalt)
    { // Zuweisung behält altes Blatt oder das neue
        Blatt->rechts = Einfuegen(Blatt->rechts, Inhalt);
    }
    return Blatt; // gib das aktuelle Blatt zurück
}

Das Einhängen des neu angelegten Blatts im Baum erfolgt nicht in dem Durchlauf, in dem new aufgerufen wird, sondern in der davor aufgerufenen Funktion an der folgenden Stelle: 

Blatt->links = Einfuegen(Blatt->links, Inhalt);

In den meisten Fällen wird diese Zuweisung das Blatt nicht verändern, weil das als erster Parameter übergebene Blatt exakt das ist, das vorher an dieser Stelle im Baum stand. Nur wenn Blatt->links 0 war, dann wird ein neues Blatt erzeugt. Der Zeiger auf das neue Blatt wird zurückgegeben und an dieser Stelle in den Baum eingehängt.

Übung

Türme von Hanoi

Als nächstes Beispiel zum Thema Rekursion möchte ich Ihnen das Spiel >>Türme von Hanoi<< vorstellen. Sie kennen vielleicht das Geduldspiel mit den drei Stäben. Auf dem linken Stab liegen mehrere wohl geordnete Scheiben unterschiedlicher Größe übereinander. Dabei liegt die größte Scheibe zu unterst. Das Spiel besteht darin, die Scheiben auf den rechten Stab umzuschichten. Dabei darf immer nur eine Scheibe angefasst werden und niemals eine Scheibe auf einer kleineren Scheibe zu liegen kommen. Abbildung (pichanoi1) zeigt die Ausgangsposition.

An dieser Stelle steht im Buch die Abbildung "Türme von Hanoi" (pichanoi1)

Vollständige Induktion

Es gibt einen Beweis, dass das Spiel für beliebig viele Scheiben immer lösbar ist. Dazu wird die vollständige Induktion verwendet, die auch die Basis für das rekursive Verfahren liefert, um das Problem mit einem Programm zu lösen. Das Beweisverfahren der vollständigen Induktion besteht aus zwei Phasen: Die erste Phase ist die Verankerung, in der bewiesen wird, dass die Behauptung für ein Element gilt. Die zweite Phase ist der Induktionsschritt. Hier wird angenommen, dass die Behauptung für n Elemente gilt. Daraus muss bewiesen werden, dass die Behauptung auch für n+1 Elemente gilt. Gelingt der Beweis für den Schritt und ist der Nachweis für ein Element gelungen, dann gilt die Behauptung natürlich auch für zwei Elemente. Aus dem Schritt lässt sich dann folgern, dass die Behauptung auch für die jeweils nächste Anzahl, also drei, vier und so weiter gilt. Beweis:
Verankerung:
Wenn der Turm nur aus einer Scheibe besteht, kann man diese einfach vom linken Stab auf den rechten legen.
Schritt:
Es wird bewiesen, dass man einen Turm aus n+1 Scheiben korrekt umsetzen kann, sofern dies für n Scheiben funktioniert. Wir gehen von der Situation aus, dass sich auf dem linken Stab n+1 Scheiben befinden.

Die obersten n Scheiben werden auf den mittleren Stab gesetzt. Nach der Voraussetzung ist das ja möglich.

Auf dem linken Stab verbleibt eine Scheibe, die auf den dritten Stab verlegt wird.

Dann werden die n Scheiben vom mittleren Stab auf den rechten Stab gelegt. Anschließend liegen n+1 Scheiben auf dem rechten Stab.

Damit ist bewiesen, dass n+1 Scheiben umgesetzt werden können, wenn es möglich ist, n Scheiben regelkonform zu versetzen.

Programm

Die rekursive Funktion Ziehe() realisiert genau den Induktionsschritt. Sie prüft zunächst das Rekursionsende. Das tritt ein, wenn keine Scheibe mehr vorliegt. Dann ruft sie sich selbst mit n-1 Scheiben auf, um den Stapel vom Ausgangsstab zum freien Stab zu verschieben. Danach wird die unterste Scheibe verschoben. Das wird einfach durch die Bildschirmausgabe realisiert. Es wird angezeigt, von welchem Stab zu welchem Stab die Scheibe umgesetzt werden muss. Danach werden die n-1 Scheiben auf die große Scheibe gesetzt. Dazu ruft die Funktion wieder sich selbst auf.

Freiplatz

Der freie Platz wird mit einem kleinen Trick bestimmt. Die Funktion weiß durch die Parameter, welche Stäbe belegt sind. Der übrige Stab muss frei sein. Auf diesen muss der Reststapel versetzt werden. Die Summe der Stabnummern ist immer 1+2+3=6. Wenn zwei der Stäbe bekannt sind, brauchen Sie sie nur addieren, und der dritte muss die Differenz zu 6 sein.

[Türme von Hanoi rekursiv (hanoi.cpp)] 

#include <iostream>
using namespace std;

void Ziehe(int von, int nach, int ScheibenZahl)
{
    int frei;
    if (ScheibenZahl==0) return;
    frei = 6 - von - nach;    // bestimme den freien Platz
    Ziehe(von, frei, ScheibenZahl-1);
    cout << von << " - " << nach << endl;
    Ziehe(frei, nach, ScheibenZahl-1);
}

int main()
{
   Ziehe(1, 3, 3); // von 1 nach 3, 3 Scheiben
}

Der erste Aufruf zeigt, dass die Scheiben zunächst auf Stab 1 liegen, dass sie auf Stab 3 versetzt werden sollen und dass es drei Scheiben sind. Das Programm zeigt das folgende Ergebnis: 

1 - 3
1 - 2
3 - 2
1 - 3
2 - 1
2 - 3
1 - 3
Um also das Spiel für drei Scheiben zu lösen, legen Sie zunächst die Scheibe von Stab~1 auf Stab~3. Dann wird die nächste Scheibe von Stab~1 auf Stab~2 gelegt. Wenn Sie dieser Anleitung folgen, können Sie das Spiel auflösen.

Beispiel: Taschenrechner

Auch im Compilerbau werden Rekursionen intensiv eingesetzt. Als ein etwas größeres Beispiel wird hier ein Programm vorgestellt, das einfache Rechenaufgaben lösen kann. Das Programm wertet eine Zeichenkette aus. Wenn Sie diese Funktionen in Ihr Programm als Zahleneingabe einbauen, können Anwender auch einfache Grundrechenarten eingeben, wie sie sie aus Tabellenkalkulationen kennen. Die erste Stufe ist die so genannte lexikalische Analyse. Hier werden Textelemente wie Rechenoperatoren oder Zahlenkonstanten identifiziert und zu Tokens zusammengefasst.

Token

Der Aufzählungstyp tToken zeigt, welche Symbole erkannt werden. Neben den vier Grundrechenarten (PLUS, MINUS, MUL, DIV) sind dies die Klammern (LPAR und RPAR) und die Zahlen (NUMBER). Das Symbol END zeigt das Eingabeende an, und das Symbol ERROR wird benötigt, um Eingabefehler zu kennzeichnen.

sucheToken()

Die Funktion sucheToken() erkennt die Symbole und ist in der Lage, einen ganzzahligen Wert zu ermitteln.

[Lexikalische Analyse (calc.cpp)] 

enum tToken 
{
    PLUS, MINUS, MUL, DIV, LPAR, RPAR, NUMBER, END, ERROR
};

// Globale Variablen:
tToken aktToken;        // das zuletzt erkannte Token
double TokenZahlenWert; // der Wert bei Zahlenkonstanten

char *srcPos;           // Programm-Position

tToken sucheToken()
// Sucht ab der aktuellen Stringposition das nächste Token.
// Hier werden auch die Zahlenkonstanten bestimmt und in
// der globalen Variablen TokenZahlenWert abgelegt.
{
    aktToken = ERROR;
    if (*srcPos==0)
    {
        aktToken = END;
    } 
    else 
    {
        switch (*srcPos)
        {
            case '(': aktToken=LPAR;  break;
            case ')': aktToken=RPAR;  break;
            case '*': aktToken=MUL;   break;
            case '/': aktToken=DIV;   break;
            case '+': aktToken=PLUS;  break;
            case '-': aktToken=MINUS; break;
        }
        if (*srcPos>='0' && *srcPos<'9') 
        {
            aktToken=NUMBER;
            TokenZahlenWert = 0.0;
        }
        while (*srcPos>='0' && *srcPos<'9') 
        {
            TokenZahlenWert *= 10;
            TokenZahlenWert += *srcPos-'0';
            srcPos++;
        }
        if (aktToken != NUMBER)
        {
            srcPos++;
        }
    }
    return aktToken;
}

tToken Error(char *s)
// Meldung ausgeben und Fehler-Token zurückliefern
{
    cerr << s << endl;
    return ERROR;
}

Die Rekursion wird verwendet, wenn das Programm beginnt, die Tokens als Anweisungen zu interpretieren und dabei Klammern und Prioritäten berücksichtigt. Zuerst wird die Funktion aufgerufen, die die Operation mit der niedrigsten Priorität auswertet. Das ist im Beispiel die Funktion PlusMinus(). Diese ruft sofort die Behandlung der Punktrechnung in der Funktion MulDiv() auf. Und auch diese Funktion wendet sich zuerst an die Funktion Klammern(). Die Klammern haben wie die Vorzeichen die höchste Priorität. Entsprechend prüft die Funktion Klammern(), ob ein Token vorliegt, das ihrer Prioritätsstufe entspricht. Dazu gehört die öffnende Klammer, eine Zahl oder ein Vorzeichen. Ist das vorliegende Token keines dieser Elemente, endet die Funktion und springt somit zur aufrufenden Funktion MulDiv() zurück. Diese schaut nach dem Stern oder dem Schrägstrich. Erst wenn auch das nicht passt, kehrt der Aufruf wieder zu PlusMinus() zurück und wertet die Addition oder Subtraktion aus.

Rekursiver Abstieg

Wenn aber die Funktion Klammern() fündig geworden ist und eine linke Klammer gefunden hat, dann ruft sie PlusMinus() auf, um den eingeklammerten Ausdruck zu analysieren. Da die Funktion Klammern() durch PlusMinus() aufgerufen wurde, handelt es sich hier um eine indirekte Rekursion.

[Parser (calc.cpp)] 

double PlusMinus(); // Prototyp

double Klammern()
// wertet Klammern, Zahlen und Vorzeichen aus
// ruft Klammern() und PlusMinus() dadurch rekursiv auf!
{
    double Wert;
    switch(aktToken)
    {
        case NUMBER:
            sucheToken();
            return TokenZahlenWert;
        case MINUS:
            sucheToken();
            return -Klammern();
        case LPAR:
            sucheToken();
            Wert = PlusMinus();
            if (aktToken != RPAR)
            {
               return Error(") expected");
            }
            sucheToken();
            return Wert;
        case END:
            return 1;
    }
    return Error("primary expected");
}

double MulDiv()
// wertet Multiplikation und Division aus
// ruft Klammern() auf, dadurch rekursiv!
{
    double Wert;
    // rufe erst die Operation mit der nächsthöheren
    // Priorität auf
    Wert = Klammern();
    while (aktToken==MUL || aktToken==DIV)
    {
        if (aktToken==MUL)
        {
            sucheToken();
            Wert *= Klammern();
        }
        else if (aktToken==DIV)
        {
          sucheToken();
          Wert /= Klammern();
        }
    }
    return Wert;
}

double PlusMinus()
// wertet Summe und Differenz aus
// ruft MulDiv() auf, dadurch rekursiv
{
    double Wert;
    // rufe erst die Operation mit der nächsthöheren
    // Priorität auf
    Wert = MulDiv();
    while (aktToken==PLUS || aktToken==MINUS)
    {
        if (aktToken==PLUS)
        {
            sucheToken();
            Wert += MulDiv();
        }
        else if (aktToken==MINUS)
        {
            sucheToken();
            Wert -= MulDiv();
        }
    }
    return Wert;
}

double Auswertung(char *s)
{
    srcPos = s;
    sucheToken();      // bestimme das erste Token vorweg
    return PlusMinus();
}

int main(int argc, char* argv[])
{
    double Wert = Auswertung(argv[1]);
    cout << Wert << endl;
    return 0;
}

Der Aufruf der Funktion Auswertung() erfordert als Parameter nur die Zeichenkette, in der sich der auszuwertende Ausdruck befindet. Die Eingabe darf keine Leerzeichen enthalten und ist auf ganzzahlige Eingaben beschränkt, da die Funktion sucheToken() derzeit keine Nachkommastellen auswertet. An anderer Stelle finden Sie Lösungen, die auch dieses Problem beseitigen.

Aufruf

Das Programm erhält seinen auszuwertenden String als ersten Parameter. Unter UNIX ist darauf zu achten, dass Sie diesen in Anführungszeichen setzen, sobald Sie eine Multiplikation ausführen wollen.[1] Hier sehen Sie ein paar Testläufe: 

> calc "12*(5+2)"
84
> calc "4*(5+2)"
28
> calc "4*5+2"
22
> calc "(5-4)*5*6+(7-3)*((4+2))"
54
> calc "(5-4)*5*6+(7-3)*((4+5)/3)"
42
>

Der Rechner kommt mit der Punkt-vor-Strich-Regel klar, hat kein Problem mit Klammern und kann auch komplexere Ausdrücke ausrechnen.

Übungsaufgaben

[1]
Der Grund ist, dass die UNIX-Shell einen Stern als Platzhalter für Dateien interpretieren wird und dadurch drollige Ergebnisse zu erwarten sind.

Diese Seite basiert auf Inhalten aus dem Buch Arnold Willemer: Einstieg in C++
Mit freundlicher Genehmigung und Unterstützung des Verlags galileo computing

Informatik-Ecke Einstieg in C++ (C) Copyright 2005 Arnold Willemer