Rekursionen sind etwas schwierig zu verstehen aber ungeheuer mächtig. In allen Situationen, in denen auf baumähnlichen Strukturen gearbeitet werden, ist eine Rekursion kaum zu umgehen.

• Countdown
• Fibonacci
• Fakultät
• Sinn und Unsinn rekursiver Funktionen
• Beispiel: Einbindung von Dateiinhalten
• Beispiel: binärer Baum
• Türme von Hanoi
• Videos
• Beispiel: Taschenrechner

• Rekursionen in C++
• Rekursion in Python
• Rekursion in Java

Countdown

// Java
class CountDown {

    static void countDown(int n) {
        if (n>0) {
          System.out.println(n);
          countDown(n-1);
        }
    }

    public static void main(String[] args) {
        countDown(10);
    }
}

// C/C++
#include <iostream>

void countDown(int n)
{
    if (n>0)
    {
      std::cout << n << std::endl;
      countDown(n-1);
    }
}

int main()
{
    countDown(10);
}

Die Wiederholung erfolgt nicht durch eine Schleife, sondern dadurch, dass sich die Methode countDown selbst aufruft - die sogenannte Rekursion.

Jeder Aufruf einer Methode führt dazu, dass die Aufrufposition gespeichert wird, damit die Methode dorthin zurückkehren kann. Neben der Rücksprungadresse werden dort auch alle lokalen Variablen inklusive der Parameter wieder hergestellt, so dass der Rücksprung in die ursprüngliche Situation möglich ist.

Wie jede Schleife muss auch die Rekursion ein Ende haben. Dazu muss die Endebedingung sauber formuliert werden. Ansonsten kommt es zu einer Endlosschleife. Im Falle einer Rekursion läuft dann der Stapelspeicher über, der die Rücksprungadresse und die lokalen Variablen aufnimmt, der sogenannte Stack-Overflow.

Im Falle des Countdowns wird die Endebedingung durch die if-Anweisung definiert, die vor dem rekursiven Aufruf steht.

Beim Selbstaufruf von countDown wird irgendwann der Parameter 0 und die Abfrage greift nicht mehr. Stattdessen kehrt die Methode zu ihrem Aufrufer zurück, der eben sie selbst ist. Aber dort passiert nichts mehr. Sie läuft auch hier auf das Methodenende. Das geschieht so lange, bis sie zu ihrem Aufrufer zurückkehrt.

Nutzung des Stacks

Umgekehrt

// Java
class CountDown {

    static void countDown(int n) {
        if (n>0) {
          countDown(n-1);
          System.out.println(n);
        }
    }

    public static void main(String[] args) {
        countDown(10);
    }
}

// C/C++
#include <iostream>

void countDown(int n)
{
    if (n>0)
    {
      countDown(n-1);
      std::cout << n << std::endl;
    }
}

int main()
{
    countDown(10);
}

Fakultät

fakultaet(n) = 1 * 2 * ... * n

Die Berechnung kann rekursiv erfolgen. Dabei errechnet man die Fakultät von n als die Multiplikation von n mit der Fakultät von (n-1) und so weiter. Damit ergibt sich eine Funktion folgender Art:

long fakultaet(int n) {
    if (n>1) {
        return n * fakultaet(n-1);
    }
    return 1;
}

long iterfakultaet(int n) {
    long f = 1;
    for (int i=2; i<=n; i++) {
        f = f * i;
    }
    return f;
}

Fibonacci

Die Fibonacci-Folge ist eine Folge ganzer Zahlen, in der sich jedes Element aus der Summe seiner beiden Vorgänger bildet.

fibonacci(n) = fibonaci(n-1) + fibonaci(n-2)

Für Youtube-Fans hier die Erklärung von Christian Spannagel.

Die Bildung eines Elements der Folge über deren Vorgänger nennt man rekursiv. In C/C++ oder Java ausgedrückt ergibt sich folgende Funktion:

int fibonacci(int n)
{
    if (n <= 1)
        return 1;
    else
        return fibonacci(n-1) + fibonacci(n-2);
}

long iterfibonacci(int n) {
    long a = 1, b = 1, f = 1;
    for (int i=1; i<n; i++) {
        f = a + b; a = b; b = f;
    }
    return f;
}

Sinn und Unsinn rekursiver Funktionen

Sobald es aber um Probleme geht, die auf baumartigen Strukturen basieren, geht an der Rekursion kein vernünftiger Weg vorbei.

               +----+         
               | 12 |         
               +----+         
               /    \         
          +----+    +----+    
          |  7 |    | 17 |    
          +----+    +----+    
          /    \         \    
     +----+    +----+    +----+
     |  3 |    |  9 |    | 22 |
     +----+    +----+    +----+
     /
+----+                        
|  2 |                        
+----+

Wie würden Sie beispielsweise einen binären Baum wie den obigen mit einer normalen Schleife durchlaufen? Eine rekursive Funktion dafür ist recht kurz.

void ausgeben(Knoten knoten) {
    if (knoten.links!=null) {
        ausgeben(knoten);
    }
    System.out.println(knoten.zahl);
    if (knoten.rechts!=null) {
        ausgeben(knoten);
    }
}

• Solange auf dem linken Ast noch ein Knoten folgt, wird die Funktion sich selbst mit diesem Nachfolger aufrufen. Zuvor wird sie ihre Position im Programm und die lokalen Variablen inklusive Parameter auf dem Stack speichern. Kommt sie also vom Aufruf zurück, ist alles wie zuvor.
• Hat sich die Funktion oft genug aufgerufen, landet sie bei der 2. Hier gibt es keinen linken Nachfolger. Es gibt keinen rekursiven Aufruf mehr.
• Nun wird die Ausgabe (System.out.prinln) der Zahl des Knotens auf dem Bildschirm ausgegeben.
• Anschließend wird geprüft, ob es einen rechten Ast gibt.
• Das ist nicht der Fall. Die Funktion endet und springt in den Zustand hinter dem Aufruf, als sie auf dem Knoten mit der 3 stand. Die 3 wird ausgegeben. Einen rechten Ast gibt es nicht. Die Funktion kehrt zurück.
• Nun ist sie wieder im Zustand, als sie den Knoten mit der 7 bearbeitete. Sie gibt die 7 aus.
• Hier gibt es einen rechten Ast. Sie ruft sich mit dem Knoten mit der 9 auf.
• Diese hat keinen linken Ast, sonst würde sie ihn hinabsteigen.
• Stattdessen gibt die Funktion die 9 aus, stellt keinen rechten Ast fest und kehrt zurück.
• Der Rest des Baums wird auf diese Weise abgearbeitet. Tatsächlich wird der gesamte Baum sauber durchlaufen.

Beispiel: Einbindung von Dateiinhalten

Mit Schleifen bekommen Sie das nur schwer in den Griff, da das Programm nach Auswertung einer Datei an die Stelle zurückkehren muss, an der es zuletzt gewesen ist. Das folgende Skelett einer Funktion zeigt, wie das Problem durch eine Rekursion zu lösen ist.

include(char * DateiName)
{
    oeffneDatei(DateiName)
    while (!endeDerDatei())
    {
        liesZeile();
        if (enthaeltInclude(IncludeDateiName))
        {
             include(IncludeDateiName);
        }
        werteAus();
    }
    schliesseDatei();
}

Eine solche Funktion kommt mit beliebig verschachtelten #include-Befehlen zurecht. Übrigens finden Sie bei TeX bzw. LaTeX mit dem Befehl input einen ähnlichen Befehl.

Beispiel: binärer Baum

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 Knoten
{
    int zahl;
    Knoten * links;
    Knoten * rechts;
};

public class Knoten {
    public int zahl;
    public Knoten links;
    public Knoten rechts;
}

Ein Baum entsteht, wenn mehrere Knoten durch die Zeiger links oder rechts miteinander verbunden werden. 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 in C/C++ an den Zeigernamen die Zeichenkombination -> gefolgt vom Elementnamen angehängt, in Java werden beide durch einen Punkt getrennt. Das Hauptprogramm soll einen Baum aufbauen, indem die Funktion einfuegen für alle Elemente eines Arrays aufgerufen wird. Zum Test soll der Baum dann ausgegeben werden.

int main()
{
    Knoten *baum = new Knoten;
    baum->zahl = 12;
    int zahlen[6] = { 7, 17, 3, 9, 22, 2 };
    for (int i=0; i<6; i++)
    {
        baum = einfuegen(baum, zahlen[i]);
    }
    ausgeben(baum);
}

public static void main(String[] args) {
    int zahlen[] = { 7, 17, 3, 9, 22, 2 };
    Knoten baum = new Knoten();
    baum.zahl = 12;
    for (int zahl : zahlen) {
        baum = einfuegen(baum, zahl);
    }
    ausgeben(baum);
}

Binärbaum füllen

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.

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

static Knoten einfuegen(Knoten blatt, int inhalt)
{
    if (blatt==null) // Freie Position gefunden
    { // Neues Blatt einfügen
        blatt = new Knoten();
        blatt.links = blatt.rechts = null;
        blatt.zahl = inhalt;
        return blatt; // Zeiger auf neues Blatt zurückgeben
    }
    if (inhalt < blatt.zahl)
    { // Zuweisung behält altes Blatt oder das neue
        blatt.links = einfuegen(blatt.links, inhalt);
    }
    else if (inhalt > blatt.zahl)
    { // Zuweisung behält altes Blatt oder das neue
        blatt.rechts = einfuegen(blatt.rechts, inhalt);
    }
    return blatt; // gib das aktuelle Blatt zurück
}

blatt->links = einfuegen(blatt->links, zahl);

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

Auslesen

void ausgeben(Knoten *knoten) {
    if (knoten->links) {
        ausgeben(knoten->links);
    }
    std::cout << knoten->zahl << std::endl;
    if (knoten->rechts) {
        ausgeben(knoten->rechts);
    }
}

static void ausgeben(Knoten knoten) {
    if (knoten.links!=null) {
        ausgeben(knoten.links); // -- pos1 --
    }
    System.out.println(knoten.zahl);
    if (knoten.rechts!=null) {
        ausgeben(knoten.rechts); // -- pos2 --
    }
}

Übung

• Schreiben Sie eine rekursive Funktion, die Zahlen in einem Binärbaum sucht.

Türme von Hanoi

Vollständige Induktion

Verankerung:

In der Verankerung der vollständigen Induktion wird gezeigt, dass das Problem für 1 lösbar ist. Wenn der Turm nur aus einer Scheibe besteht, kann man diese einfach vom linken Stab auf den rechten legen. Das war also ganz leicht.

Induktionsschritt:

Es muss gezeigt werden, dass wenn es für eine beliebige Zahl n gilt, auch für n+1 gilt.

Es wird also 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. Der ist ja noch leer.

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.

Damit ist es bewiesen, dass man die Türme von Hanoi lösen kann, egal wie viele Scheibe auf dem linken Stab sind. Für 1 haben wir es gezeigt. Wenn 1 geht, dann muss aus dem Induktionsschritt folgen, dass 1+1, also 2 auch geht. Dann geht es auch für 3 und so weiter.

Programm

Freiplatz

#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
}

public class Hanoi {

    static void hanoi(int scheiben, char start, char end, char mitte) {
        if (scheiben == 1){
            System.out.println("von "+start+" nach "+end);
        } else {
            hanoi(scheiben - 1, start, mitte, end);
            System.out.println("von "+start+" nach "+end);
            hanoi(scheiben - 1, mitte, end, start);
        }
    } 

    static public void main(String[] args){
            hanoi(3, 'A', 'B', 'C');
    }
}

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

Beispiel: Taschenrechner

Wenn Sie diese Funktionen in Ihr Programm für die 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

sucheToken()

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 erst 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

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.

Aufruf

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.

Videos

Rekursionen

Rekursionen T.2 Bäume

Übungsaufgaben

• An anderer Stelle finden Sie ein Beispiel, wie Sie aus einer Zeichenkette Fließkommazahlen auslesen. Integrieren Sie dies in den kleinen Taschenrechner, damit er auch mit Werten vom Typ double umgehen kann.
• Ergänzen Sie den Taschenrechner dahingehend, dass in der Eingabe auch Leerzeichen zwischen den Tokens stehen können. Beim Test sollten Sie die Eingaben mit Leerzeichen in Anführungszeichen setzen. Ansonsten wird Ihre Eingabezeile auf mehrere Parameter verteilt.
• Warum kommt der Interpreter mit dem Minus nicht durcheinander, obwohl es einmal als Vorzeichen und einmal als Operator verwendet wird?