C++-Programmierung/ Weitere Grundelemente/ Schleifen mal anders – Rekursion
Aus Wikibooks
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, wenn Sie so schneller ein richtiges Ergebnis erhalten als beim Schreiben einer iterativen 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.
[Bearbeiten] 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:
unsigned int fakultaet(unsigned int zahl) {
if (zahl <= 1) {
return 1; // Die Fakultät von 0 und 1 ist als 1 definiert.
}
return fakultaet(zahl - 1) * zahl;
}
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) << "!" << endl;
}
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 wert = 1;
for (unsigned int i = 2; i <= zahl; ++i) {
wert *= i;
}
return wert;
}
[Bearbeiten] Fibonacci-Zahlen
Als zweites Beispiel wollen wir Fibonacci-Zahlen ausrechnen.
unsigned int fibonacci(unsigned int zahl) {
if (zahl == 0) { // Die Fibonacci-Zahl von null ist null
return 0;
}
if (zahl == 1) { // Die Fibonacci-Zahl von eins ist eins
return 1;
}
// 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) << "!" << endl;
}
Die Fibonacci-Zahl von 12 ist 144!
Die iterative Entsprechung sieht folgendermaßen aus:
if (zahl == 0) { // Die Fibonacci-Zahl von null ist null
return 0;
}
if (zahl == 1) { // Die Fibonacci-Zahl von eins ist eins
return 1;
}
unsigned int ret;
unsigned int h1 = 0;
unsigned int h2 = 1;
for (unsigned int i = 1; i < zahl; ++i) {
ret = h1 + h2; // Ergebnis ist die Summe der zwei vorhergehenden Fibonacci-Zahlen
h1 = h2; // und den beiden Hilfsvariablen die
h2 = ret; // neuen vorhergehenden Fibonacci-Zahlen
}
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.
