Menü

Rekursion in C ++

recursion c

Versuchen Sie Unser Instrument, Um Probleme Zu Beseitigen

Entdecken Sie alles über Rekursion in C ++ mit klassischen Beispielen.

In unserem vorherigen Tutorial haben wir mehr über Funktionen in C ++ erfahren.

Neben der Verwendung der Funktionen zum Aufteilen des Codes in Untereinheiten und zum Vereinfachen und Lesen des Codes sind Funktionen in verschiedenen anderen Anwendungen nützlich, einschließlich der Lösung von Echtzeitproblemen, der mathematischen und statistischen Berechnung.

Bei der Entwicklung komplexerer Anwendungen in C ++ stoßen wir auf viele Anforderungen, sodass wir einige spezielle Konzepte von C ++ anwenden müssen. Rekursion ist ein solches Konzept.

=> Besuchen Sie hier für die vollständige Liste der C ++ - Tutorials.

REKURSION IN C ++

In diesem Tutorial erfahren Sie mehr über die Rekursion, wo und warum sie zusammen mit einigen klassischen C ++ - Beispielen verwendet wird, die die Rekursion implementieren.

Was du lernen wirst:

Was ist Rekursion?

Rekursion ist ein Prozess, bei dem sich eine Funktion selbst aufruft. Die Funktion, die die Rekursion implementiert oder sich selbst aufruft, wird als rekursive Funktion bezeichnet. Bei der Rekursion ruft sich die rekursive Funktion immer wieder auf und fährt fort, bis eine Endbedingung erfüllt ist.

Das folgende Bild zeigt, wie Rekursion funktioniert:

Arbeiten der Rekursion

Wie wir im obigen Diagramm sehen, ruft die Hauptfunktion eine Funktion auf, funct (). Die Funktion funct () ruft sich wiederum innerhalb ihrer Definition auf. So funktioniert die Rekursion. Dieser Prozess des Funktionsaufrufs selbst wird fortgesetzt, bis wir eine Abschlussbedingung bereitstellen, die ihn beendet.

Normalerweise stellen wir während der Implementierung der Rekursion eine Codeverzweigung bereit, sodass wir eine Bedingung bereitstellen, die eine Rekursion auslöst, und eine andere, um die normale Ausführung auszuführen.

Rekursionsgrundbedingung

Wenn eine Rekursion durchgeführt wird, wird die Lösung für den Basisfall oder den Abschlussfall bereitgestellt und die Lösungen für größere Probleme werden basierend auf den Lösungen für kleinere Probleme erstellt.

Betrachten wir ein klassisches Beispiel für Rekursion, die faktorielle Notation.

Wir wissen, dass mathematisch die Fakultät einer Zahl n ist:

n! = nxn-1x… .x0!
vorausgesetzt, dass 0! = 1;

Die Fakultät für n = 3 ist also 3! = 3 × 2!

3! = 3x2x1!
3! = 3x2x2x0!
3! = 3x2x1x1 = 6

So programmatisch können wir diese Berechnung wie folgt ausdrücken:

int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); }

Wie oben gezeigt, haben wir die obige Berechnung einer Fakultät in einen rekursiven Funktionsaufruf ausgedrückt. Wir sehen, dass wenn die Zahl n kleiner oder gleich 1 ist, wir 1 anstelle eines rekursiven Aufrufs zurückgeben. Dies wird als Grundbedingung / Fall für die Fakultät bezeichnet, die das Stoppen der Rekursion ermöglicht.

Daher entscheidet die Grundbedingung grundsätzlich, wie oft sich eine rekursive Funktion selbst aufrufen soll. Dies bedeutet, dass wir die Fakultät einer größeren Zahl sehr gut berechnen können, indem wir sie in kleineren Zahlen ausdrücken, bis die Basisklasse erreicht ist.

Im Folgenden finden Sie ein perfektes Beispiel für die Berechnung der Fakultät einer Zahl:

#include #include using namespace std; int factorial(int n){ if(n <=1) return 1; else return n*factorial(n-1); } int main() { int num,result; cout<>num; result = factorial(num); cout<

Ausgabe:

Geben Sie die Zahl ein, deren Fakultät berechnet werden soll: 10
10! = 3628800

Im obigen Beispiel implementieren wir die Rekursion. Wir nehmen die Zahl, deren Fakultät zu finden ist, aus der Standardeingabe und übergeben sie dann an die Fakultätsfunktion.

In der Fakultätsfunktion haben wir die Grundbedingung als (n<=1). So, when the base case is reached, the function returns. Using this base case, we can calculate factorial of any number greater than 1.

Speicherzuordnung für den rekursiven Aufruf

Wir wissen, dass beim Ausführen eines Funktionsaufrufs der Status der aufrufenden Funktion auf dem Stapel gespeichert wird. Wenn ein Funktionsaufruf abgeschlossen ist, wird dieser Status wiederhergestellt, damit das Programm die Ausführung fortsetzen kann.

Wenn ein rekursiver Funktionsaufruf ausgeführt wird, wird der Status oder Speicher für die aufgerufene Funktion zusätzlich zum Status der aufrufenden Funktion zugewiesen, und für jeden rekursiven Funktionsaufruf wird eine andere Kopie der lokalen Variablen erstellt.

Wenn die Grundbedingung erreicht ist, kehrt die Funktion zur aufrufenden Funktion zurück und der Speicher wird freigegeben und der Prozess wird fortgesetzt.

Stapelüberlauf in Rekursion

Wenn die Rekursion unbegrenzt lange fortgesetzt wird, kann dies zu einem Stapelüberlauf führen.

Wann kann die Rekursion so fortgesetzt werden? Eine Situation ist, wenn wir die Grundbedingung nicht angeben. Eine andere Situation ist, wenn die Grundbedingung beim Ausführen eines Programms nicht erreicht wird.

Zum Beispiel,Wir modifizieren das obige Fakultätsprogramm und ändern seine Grundbedingung.

int factorial(int n){ if(n ==1000) return 1; else return n*factorial(n-1); }

Im obigen Code haben wir die Grundbedingung in (n == 1000) geändert. Wenn wir nun die Zahl n = 10 geben, können wir schließen, dass die Grundbedingung niemals erreicht wird. Auf diese Weise wird irgendwann der Speicher auf dem Stapel erschöpft, was zu einem Stapelüberlauf führt.

Daher müssen wir beim Entwerfen rekursiver Programme vorsichtig mit der Grundbedingung sein, die wir bereitstellen.

Direkte Vs indirekte Rekursion

Bisher haben wir in der Rekursion gesehen, wie sich die Funktion selbst aufruft. Dies ist die direkte Rekursion.

Es gibt eine andere Art der Rekursion, d. H. Die indirekte Rekursion. Dabei ruft eine Funktion eine andere Funktion auf und diese Funktion ruft dann die aufrufende Funktion auf. Wenn f1 und f2 zwei Funktionen sind. Dann ruft f1 f2 auf und f2 ruft wiederum f1 auf. Dies ist eine indirekte Rekursion.

Ist der Netzwerksicherheitsschlüssel mit dem WLAN-Passwort identisch?

L. Lassen Sie uns unser Fakultätsprogramm überarbeiten, um eine direkte Rekursion zu demonstrieren.

#include #include using namespace std; int factorial_b(int); int factorial_a(int n){ if(n <=1) return 1; else return n*factorial_b(n-1); } int factorial_b(int n){ if(n <=1) return 1; else return n*factorial_a(n-1); } int main() { int num, result; cout<>num; result = factorial_a(num); cout<

Ausgabe:

Geben Sie die Zahl ein, deren Fakultät berechnet werden soll: 5
5! = 120

Im obigen Beispiel haben wir eine indirekte Rekursion gezeigt. Die Hauptfunktion ruft Fakultät_a auf. Factorial_a ruft factorial_b auf. Factorial_b ruft wiederum factorial_a auf. Wir sehen, dass die Ausgabe des Programms nicht betroffen ist.

Rekursion mit und ohne Schwanz

Eine endständige rekursive Funktion ist eine rekursive Funktion, bei der der letzte Aufruf in der Funktion ausgeführt wird.

Zum BeispielBetrachten Sie die folgende Funktion.

void display(int n){ if(n<=1) return; cout<<” ”<

Im obigen Beispiel ist die Anzeige eine endständige rekursive Funktion, so dass es sich um den letzten Funktionsaufruf handelt.

Tailed-Funktionen gelten als besser als nicht-Tailed-rekursive Funktionen, da sie vom Compiler optimiert werden können. Der Grund ist, dass, da der endrekursive Aufruf die letzte Anweisung in der Funktion ist, nach diesem Aufruf kein Code mehr ausgeführt werden muss.

Daher ist das Speichern des aktuellen Stapelrahmens für die Funktion nicht erforderlich.

Vor- und Nachteile der Rekursion gegenüber der iterativen Programmierung

Rekursive Programme bieten kompakten und sauberen Code. Ein rekursives Programm ist eine einfache Methode zum Schreiben von Programmen. Es gibt einige inhärente Probleme wie Fakultät, Fibonacci-Sequenz, Türme von Hanoi, Baumdurchquerungen usw., die zur Lösung eine Rekursion erfordern.

Mit anderen Worten, sie werden durch Rekursion effizient gelöst. Sie können auch durch iterative Programmierung mithilfe von Stapeln oder anderen Datenstrukturen gelöst werden. Die Implementierung kann jedoch komplexer werden.

Die Problemlösungsfähigkeiten der rekursiven und iterativen Programmierung sind gleich. Rekursive Programme benötigen jedoch mehr Speicherplatz, da alle Funktionsaufrufe auf dem Stapel gespeichert werden müssen, bis der Basisfall übereinstimmt.

Rekursive Funktionen haben aufgrund zu vieler Funktionsaufrufe und Rückgabewerte auch einen Zeitaufwand.

Beispiele für Rekursion

Als nächstes werden wir einige Beispiele für rekursive Programmierung implementieren.

Fibonacci-Serie

Die Fibonacci-Reihe ist die Sequenz, die als angegeben wird

0 1 1 2 3 5 8 13 ……

Wie oben gezeigt, sind die ersten beiden Zahlen der Fibonacci-Reihen 0 und 1. Die nächste Zahl in der Sequenz ist die Summe der beiden vorhergehenden Zahlen.

Lassen Sie uns diese Reihe mit Rekursion implementieren.

#include using namespace std; void fibSeries(int n){ static int n1=0, n2=1, n3; if(n>0){ n3 = n1 + n2; n1 = n2; n2 = n3; cout<num; cout<<'Fibonacci Series for '<

Ausgabe:

Geben Sie die Anzahl der Elemente für die Fibonacci-Reihe ein: 10
Fibonacci-Serie für 10 Zahlen: 0 1 1 2 3 5 8 13 21 34

In diesem Beispiel haben wir einen rekursiven Aufruf verwendet, um die Fibonacci-Sequenz zu generieren. Wir sehen, dass die ersten beiden konstanten Zahlen direkt gedruckt werden und für die nächsten Zahlen in der Sequenz eine rekursive Funktion verwenden.

Palindrom

Eine Palindromzahl ist eine Zahl, die beim Lesen in umgekehrter Richtung mit dem Lesen von links nach rechts identisch ist.

Zum Beispiel, Die Zahl 121 liest beim Lesen von links nach rechts und von rechts nach links dasselbe, d. h. 121. Daher ist 121 ein Palindrom.

Die Zahl 291 liest sich beim Lesen von rechts nach links, d. H. In umgekehrter Reihenfolge, wie 192. Daher ist 291 kein Palindrom.

#include using namespace std; int reverse_digits(int n, int temp) { if (n == 0) return temp; temp = (temp * 10) + (n % 10); return reverse_digits(n / 10, temp); } int main() { int num; cout<>num; int result = reverse_digits(num, 0); if (result == num) cout << 'Number '<

Ausgabe:

Geben Sie die Nummer ein, um das Palindrom zu überprüfen: 6556
Nummer 6556 ist ein Palindrom

Ein Screenshot dafür ist unten angegeben.

Rekursion - Palindrom

Im obigen Programm lesen wir die Eingabenummer von der Standardeingabe. Dann übergeben wir diese Zahl an eine rekursive Funktion, um die Ziffern einer Zahl umzukehren. Wenn die umgekehrten Ziffern und die eingegebene Nummer identisch sind, ist die Nummer ein Palindrom.

Fazit

Damit sind wir mit der Rekursion fertig. In diesem Tutorial haben wir die rekursive Programmierung, die rekursive Funktion, ihre Vor- und Nachteile sowie verschiedene Beispiele im Detail untersucht.

Abgesehen von diesen Beispielen wird die Rekursion auch zur Lösung einiger Standardprobleme wie Durchquerungen (Inorder / Preorder / Postorder), Türme von Hanoi, BFS-Durchquerung usw. verwendet.

=> Besuchen Sie hier, um C ++ von Grund auf neu zu lernen.

Literatur-Empfehlungen

^