C++-Programmierung/ Weitere Grundelemente/ Rekursion

Jede Funktion kann sowohl andere Funktionen als auch sich selbst aufrufen. Ein solcher Selbstaufruf wird auch rekursiver Aufruf genannt. Das dahinter stehende Konzept bezeichnet man entsprechend als Rekursion.

Eine Ausnahme von dieser Regel bildet wiedereinmal die Funktion main(). Sie darf ausschließlich vom Betriebssystem aufgerufen werden, also weder von einer anderen Funktion, noch aus sich selbst heraus.

Eine rekursive Problemlösung ist etwas langsamer und speicheraufwendiger als eine iterative Variante (also mit Schleifen). Dafür ist der Code allerdings auch kompakter und ein „intelligenter“ Compiler ist meist in der Lage, eine Rekursion in eine Iteration umzuwandeln um somit die Nachteile aufzuheben. Sie sollten also keine Scheu haben ein Problem mit Rekursion zu lösen, insbesondere wenn die Lösung leichter zu verstehen ist als eine iterative Variante. Sollten dadurch im Laufe der Entwicklung eines Programms Geschwindigkeits- oder Speichernachteile auftreten, so können Sie die Funktion immer noch durch eine iterativ arbeitende ersetzen.

Beispiele

Fakultät

Als erstes einfaches Beispiel einer rekursiven Problemlösung nehmen wir die Berechnung der Fakultät. Da die Fakultät für negative und nicht ganze Zahlen nicht definiert ist, benutzen wir als Datentyp unsigned int:

#include <iostream>       // Für std::cin und std::cout

unsigned int fakultaet(unsigned int zahl) {
    if (zahl <= 1) {
        return 1; // Die Fakultät von 0 und 1 ist als 1 definiert.
    } else {
        return zahl * fakultaet(zahl - 1);
    }
}

int main() {
    unsigned int zahl;

    std::cout << "Bitte Zahl eingeben: ";
    std::cin >> zahl;                           // Zahl einlesen
    std::cout << "Die Fakultät von " << zahl << // Antwort ausgeben
        " ist " << fakultaet(zahl) << "." << std::endl;
}

Ausgabe:

Bitte Zahl eingeben: <eingabe>4</eingabe>
Die Fakultät von 4 ist 24.

Genau wie bei einer Schleife, ist auch bei einer Rekursion eine Abbruchbedingung definiert (also erforderlich) und genau wie bei einer Schleife würde ohne Abbruchbedingung eine Endlosrekursion auftreten, analog zur Endlosschleife. So eine Endlosschleife bezeichnet man auch als infiniten Regress. Wenn der Wert der Variablen zahl kleiner oder gleich eins ist, so wird eins zurückgegeben, andernfalls wird weiter rekursiv aufgerufen. Eine iterative Variante für das gleiche Problem könnte folgendermaßen aussehen:

unsigned int fakultaet(unsigned int zahl) {
    unsigned int wert = 1;

    for (unsigned int i = 2; i <= zahl; ++i) {
        wert *= i;
    }

    return wert;
}

Fibonacci-Zahlen

Als zweites Beispiel wollen wir Fibonacci-Zahlen ausrechnen.

#include <iostream>

unsigned int fibonacci(unsigned int zahl) {
    if (zahl == 0) { // Die Fibonacci-Zahl von null ist null
        return 0;
    } // else
    if (zahl == 1) { // Die Fibonacci-Zahl von eins ist eins
        return 1;
    } // else

    // Ansonsten wird die Summe der zwei vorherigen Fibonacci-Zahlen zurückgegeben.
    return fibonacci(zahl - 1) + fibonacci(zahl - 2);
}

int main() {
    unsigned int zahl;

    std::cout << "Bitte Zahl eingeben: ";
    std::cin >> zahl;                                 // Zahl einlesen
    std::cout << "Die Fibonacci-Zahl von " << zahl << // Antwort ausgeben
        " ist " << fibonacci(zahl) << "." << std::endl;
}

Ausgabe:

Bitte Zahl eingeben: <eingabe>12</eingabe>
Die Fibonacci-Zahl von 12 ist 144.

Die iterative Entsprechung sieht folgendermaßen aus:

unsigned int fibonacci(unsigned int zahl) {
    if (zahl == 0) { // Die Fibonacci-Zahl von null ist null
        return 0;
    } // else
    if (zahl == 1) { // Die Fibonacci-Zahl von eins ist eins
        return 1;
    } // else

    unsigned int ret;
    unsigned int h1 = 0;
    unsigned int h2 = 1;

    for (unsigned int i = 1; i < zahl; ++i) {
        // (Zwischen-)Ergebnis ist die Summe der zwei vorhergehenden Fibonacci-Zahlen.
        ret = h1 + h2; 
        // "vorherige zwei F.-Zahlen" um 1 "Stelle" der Reihe "weiter ruecken":
        h1 = h2;
        h2 = ret;
    }

    return ret;
}

Bei vielen komplexen Problemen eignet sich Rekursion oft besser zur Beschreibung, als eine iterative Entsprechung. Aus diesem Grund trifft man das Konzept der Rekursion in der Programmierung recht häufig an. Bei der Fibonacci-Funktion ist allerdings die iterative Lösung wesentlich effizienter, da ansonsten bei jedem Aufruf dieselbe Methode wieder zweimal neu aufgerufen wird. So ergeben sich bei fibonacci(40) schon 2^40-1 Aufrufe.

Merge sort

Merge sort ist ein Beispiel für eine Funktion, bei der Rekursion sinnvoll eingesetzt wird. Die Idee ist: Um ein Array zu sortieren, sortiere erst die erste Hälfte, dann die zweite Hälfte, und dann füge die beiden Teile zusammen (merge). Der folgende Code implementiert Merge sort für int-Arrays. Sie erwartet ein Array, den ersten Index des zu sortierenden Bereichs, und den Index auf das erste Element nach dem zu sortierenden Bereich. Da die genaue Implementierung des Merge-Schritts hier nicht von Interesse ist, wird einfach angenommen, dass dafür bereits eine Funktion merge existiert.

void mergesort(int array[], int begin, int end)
{
  int mid = begin + (end-begin)/2;    // Mitte des Feldes bestimmen

  mergesort(array, begin, mid);       // Linke  Hälfte
  mergesort(array, mid, end);         // Rechte Hälfte

  merge(array, begin, mid, end);
}

Aufgabe 1: Welches wichtige Element einer Rekursion fehlt im Mergesort-Beispiel? Wie würden Sie es ergänzen?

Lösung: Es fehlt eine Abbruchbedingung. Eine mögliche Abbruchbedingung wäre: Weil eine Liste mit nur einem oder gar keinem Element darin nicht sortiert werden braucht, kann die Funktion 'nichts tun', wenn der Unterschied von begin und end kleinergleich 1 ist.

Tipp

Bei komplexeren Problemen, die rekursiv gelöst werden sollen, ist es wichtig darauf zu achten, dass das „jeweils zu lösende Problem“ bei jedem tieferen Rekursionsschritt kleiner wird, einfacher wird, näher an die Abbruchbedingung herankommt. Damit ist recht gut sichergestellt, dass die Rekursion nicht (in ungünstigen Fällen) „unendlich tief“ verzweigt.

Jeder (rekursive) Aufruf der Funktion sollte das ihr übergebene (Teil-)Problem zumindest ein wenig vereinfachen, aufteilen oder anderweitig an eine Lösung heranbringen, bevor sich die Funktion für (Unter-Teil-)Probleme rekursiv erneut aufruft - und das Vereinfachen sollte in jedem möglichen Fall (if-Zweig) geschehen.