Rekursion und einfache Abbruchfälle#

Funktionen und Programmaufbau · Lektion 26 von 60

Voraussetzungen: Funktionen, if. Lernziel: Du erkennst, wann eine Funktion sich sinnvoll selbst aufrufen kann.

Rekursion bedeutet, dass eine Funktion sich direkt oder über andere Funktionen erneut aufruft. Eine rekursive Lösung zerlegt eine Aufgabe in eine kleinere Aufgabe gleicher Form. Sie benötigt einen Basisfall, der ohne weiteren Selbstaufruf ein Ergebnis liefert.

1#include <iostream>2 3unsigned long long fakultaet(unsigned int n) {4    if (n <= 1) {5        return 1;6    }7    return n * fakultaet(n - 1);8}9 10int main() {11    unsigned int n{};12    if (!(std::cin >> n) || n > 20) {13        std::cerr << "Eine Zahl von 0 bis 20 erwartet.\n";14        return 1;15    }16    std::cout << fakultaet(n) << '\n';17}

Die Fakultät von 4 ist 4 * 3 * 2 * 1, also 24. Für 0 wird die Fakultät als 1 definiert. Die Grenze 20 sorgt hier dafür, dass das Ergebnis in den mindestens 64 Bit breiten Typ unsigned long long passt. Die Funktion hat entsprechend die Vorbedingung n <= 20; jeder andere Aufrufer muss sie ebenfalls beachten.

Was während des Aufrufs passiert#

Für fakultaet(3) wartet die äußere Funktion zunächst auf fakultaet(2), diese wiederum auf fakultaet(1). Der Basisfall liefert 1. Danach entstehen rückwärts die Ergebnisse 2 und 6.

Eine Aufrufkette hält die noch nicht beendeten Aufrufe fest. Übliche Implementierungen verwenden dafür den Call Stack, einen Stapel von Aufrufinformationen. Die Rekursionstiefe ist die Anzahl gleichzeitig aktiver rekursiver Aufrufe. Zu tiefe Rekursion kann verfügbaren Speicher überschreiten.

Wann eine Schleife besser ist#

Die Fakultät lässt sich auch mit einer einfachen Schleife berechnen. Das ist für diese lineare Aufgabe oft leichter zu überblicken. Rekursion passt besonders zu verzweigten Strukturen, etwa einem Ordnerbaum: Jeder Unterordner ist wieder ein kleinerer Ordnerbaum.

Eine rekursive Funktion wird nicht automatisch effizient. Die naive rekursive Fibonacci-Berechnung berechnet dieselben Teilaufgaben sehr oft. Memoisierung bedeutet, Ergebnisse bereits gelöster Teilaufgaben zwischenzuspeichern. Das kann unnötige Wiederholungen vermeiden.

Übung#

Welche zwei Fragen musst du bei jeder rekursiven Funktion beantworten?

Weiterlernen#

Zurück: Header, #include und mehrere Quelldateien · Kursübersicht · Weiter: Veränderbare Listen mit std::vector