Was ist Rekursion?
Der Vorgang, bei dem sich eine Funktion direkt oder indirekt selbst aufruft, wird als Rekursion und die entsprechende Funktion als rekursive Funktion bezeichnet. Mit einem rekursiven Algorithmus lassen sich bestimmte Probleme recht einfach lösen. Beispiele für solche Probleme sind Türme von Hanoi (TOH) , Inorder/Preorder/Postorder Tree Traversals , DFS von Graph usw. Eine rekursive Funktion löst ein bestimmtes Problem, indem sie eine Kopie von sich selbst aufruft und kleinere Teilprobleme der ursprünglichen Probleme löst. Bei Bedarf können viele weitere rekursive Aufrufe generiert werden. Es ist wichtig zu wissen, dass wir einen bestimmten Fall angeben müssen, um diesen Rekursionsprozess zu beenden. Wir können also sagen, dass sich die Funktion jedes Mal selbst mit einer einfacheren Version des ursprünglichen Problems aufruft.

Notwendigkeit einer Rekursion

Rekursion ist eine erstaunliche Technik, mit deren Hilfe wir die Länge unseres Codes reduzieren und das Lesen und Schreiben erleichtern können. Es hat bestimmte Vorteile gegenüber der Iterationstechnik, die später besprochen werden. Rekursion ist eine Aufgabe, die mit ihrer ähnlichen Unteraufgabe definiert werden kann und eine der besten Lösungen dafür ist. Zum Beispiel; Die Fakultät einer Zahl.

Eigenschaften der Rekursion:

• Dieselben Vorgänge mehrmals mit unterschiedlichen Eingaben ausführen.
• In jedem Schritt versuchen wir kleinere Eingaben, um das Problem zu verkleinern.
• Eine Grundbedingung ist erforderlich, um die Rekursion zu stoppen, andernfalls kommt es zu einer Endlosschleife.

Algorithmus: Schritte

The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>

Eine mathematische Interpretation

Betrachten wir ein Problem, bei dem ein Programmierer die Summe der ersten n natürlichen Zahlen bestimmen muss. Dafür gibt es mehrere Möglichkeiten, aber der einfachste Ansatz besteht einfach darin, die Zahlen beginnend bei 1 bis n zu addieren. Die Funktion sieht also einfach so aus:

Ansatz(1) – Einfach einzeln hinzufügen

f(n) = 1 + 2 + 3 +……..+ n

aber es gibt einen anderen mathematischen Ansatz, dies darzustellen,

Ansatz(2) – Rekursives Addieren

f(n) = 1 n=1

f(n) = n + f(n-1) n>1

Es gibt einen einfachen Unterschied zwischen Ansatz (1) und Ansatz (2), und zwar darin Ansatz(2) die Funktion F( ) selbst wird innerhalb der Funktion aufgerufen, daher wird dieses Phänomen als Rekursion bezeichnet, und die Funktion, die die Rekursion enthält, wird als rekursive Funktion bezeichnet. Letztendlich ist dies ein großartiges Werkzeug in der Hand der Programmierer, um einige Probleme viel einfacher und effizienter zu programmieren Weg.

Wie werden rekursive Funktionen im Speicher gespeichert?

Die Rekursion benötigt mehr Speicher, da die rekursive Funktion bei jedem rekursiven Aufruf den Stapel erweitert und die Werte dort behält, bis der Aufruf abgeschlossen ist. Die rekursive Funktion verwendet die LIFO-Struktur (LAST IN FIRST OUT) genau wie die Stapeldatenstruktur. Stack-Datenstruktur/

Was ist die Grundbedingung bei der Rekursion?
Im rekursiven Programm wird die Lösung des Basisfalls bereitgestellt und die Lösung des größeren Problems in Form kleinerer Probleme ausgedrückt.

int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }>

Im obigen Beispiel ist der Basisfall für n <= 1 definiert und der größere Wert einer Zahl kann durch Konvertierung in einen kleineren Wert gelöst werden, bis der Basisfall erreicht ist.

Wie wird ein bestimmtes Problem mithilfe der Rekursion gelöst?
Die Idee besteht darin, ein Problem anhand eines oder mehrerer kleinerer Probleme darzustellen und eine oder mehrere Grundbedingungen hinzuzufügen, die die Rekursion stoppen. Beispielsweise berechnen wir die Fakultät n, wenn wir die Fakultät von (n-1) kennen. Der Basisfall für Fakultät wäre n = 0. Wir geben 1 zurück, wenn n = 0.

Warum tritt bei der Rekursion ein Stapelüberlauffehler auf?
Wenn der Basisfall nicht erreicht oder nicht definiert ist, kann das Problem des Stapelüberlaufs auftreten. Nehmen wir ein Beispiel, um dies zu verstehen.

int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }>

Wenn Fakt(10) aufgerufen wird, werden Fakt(9), Fakt(8), Fakt(7) usw. aufgerufen, aber die Zahl wird nie 100 erreichen. Der Basisfall wird also nicht erreicht. Wenn der Speicher durch diese Funktionen auf dem Stapel erschöpft ist, kommt es zu einem Stapelüberlauffehler.

Was ist der Unterschied zwischen direkter und indirekter Rekursion?
Eine Funktion fun heißt direkt rekursiv, wenn sie dieselbe Funktion fun aufruft. Eine Funktion fun heißt indirekt rekursiv, wenn sie eine andere Funktion aufruft, beispielsweise fun_new, und fun_new fun direkt oder indirekt aufruft. Der Unterschied zwischen direkter und indirekter Rekursion ist in Tabelle 1 dargestellt.

 // An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }>

Was ist der Unterschied zwischen Tailed- und Non-Tailed-Rekursion?
Eine rekursive Funktion ist endrekursiv, wenn ein rekursiver Aufruf das letzte ist, was von der Funktion ausgeführt wird. Siehe Artikel zur Schwanzrekursion für Details.

Wie wird Speicher verschiedenen Funktionsaufrufen in der Rekursion zugewiesen?
Wenn eine Funktion von main() aufgerufen wird, wird ihr der Speicher auf dem Stapel zugewiesen. Eine rekursive Funktion ruft sich selbst auf, der Speicher für eine aufgerufene Funktion wird zusätzlich zum Speicher zugewiesen, der der aufrufenden Funktion zugewiesen ist, und für jeden Funktionsaufruf wird eine andere Kopie lokaler Variablen erstellt. Wenn der Basisfall erreicht ist, gibt die Funktion ihren Wert an die Funktion zurück, von der sie aufgerufen wurde, die Speicherzuweisung wird aufgehoben und der Prozess wird fortgesetzt.
Nehmen wir das Beispiel, wie die Rekursion funktioniert, indem wir eine einfache Funktion übernehmen.

CPP

>

>

Java

govinda

>

>

Python3

>

>

C#

>

>

PHP

>

>

Javascript

>

>

3 2 1 1 2 3>

Zeitkomplexität: O(1)
Hilfsraum: O(1)

Wann printFun(3) wird von main() aufgerufen, dem Speicher zugewiesen wird printFun(3) und ein lokaler Variablentest wird auf 3 initialisiert und die Anweisungen 1 bis 4 werden auf den Stapel gelegt, wie im folgenden Diagramm gezeigt. Zuerst wird „3“ ausgegeben. In Aussage 2, printFun(2) aufgerufen und Speicher zugewiesen wird printFun(2) und ein lokaler Variablentest wird auf 2 initialisiert und die Anweisungen 1 bis 4 werden in den Stapel verschoben. Ähnlich, printFun(2) Anrufe printFun(1) Und printFun(1) Anrufe printFun(0) . printFun(0) Geht zur if-Anweisung und kehrt zu zurück printFun(1) . Die restlichen Aussagen von printFun(1) werden ausgeführt und es kehrt zu zurück printFun(2) und so weiter. In der Ausgabe werden Werte von 3 bis 1 und dann 1 bis 3 gedruckt. Der Speicherstapel ist im folgenden Diagramm dargestellt.

Rekursion vs. Iteration

Lassen Sie uns nun einige praktische Probleme besprechen, die durch die Verwendung der Rekursion gelöst werden können, und ihre grundlegende Funktionsweise verstehen. Für ein grundlegendes Verständnis lesen Sie bitte die folgenden Artikel.
Grundlegendes Verständnis der Rekursion.
Problem 1: Schreiben Sie ein Programm und eine Wiederholungsbeziehung, um die Fibonacci-Reihe von n mit n>2 zu finden.
Mathematische Gleichung:

n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>

Wiederholungsbeziehung:

T(n) = T(n-1) + T(n-2) + O(1)>

Rekursives Programm:

 Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>

Implementierung:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

undefinierte Steigung

>

>

Javascript

>

>

Fibonacci series of 5 numbers is: 0 1 1 2 3>

Zeitkomplexität: O(2^N)
Hilfsraum: An)

Hier ist der rekursive Baum für Eingabe 5, der ein klares Bild davon zeigt, wie ein großes Problem in kleinere gelöst werden kann.
fib(n) ist eine Fibonacci-Funktion. Die zeitliche Komplexität des gegebenen Programms kann vom Funktionsaufruf abhängen.

fib(n) -> Level CBT (UB) -> 2^n-1 Knoten -> 2^n Funktionsaufruf -> 2^n*O(1) -> T(n) = O(2^n)

Für den besten Fall.

T(n) = ?(2^n2)>

Arbeiten:

Problem 2: Schreiben Sie ein Programm und eine Wiederholungsbeziehung, um die Fakultät von n zu ermitteln, wobei n>2 ist.
Mathematische Gleichung:

1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>

Wiederholungsbeziehung:

T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>

Rekursives Programm:
Eingang: n = 5
Ausgabe:
Fakultät von 5 ist: 120
Implementierung:

C++

>

>

C

>

>

Java

>

>

Python3

>

>

C#

Shweta Tiwari-Schauspieler

>

>

Javascript

>

>

factorial of 5 is: 120>

Zeitkomplexität: An)
Hilfsraum: An)

Arbeiten:

Diagramm der faktoriellen Rekursionsfunktion für Benutzereingaben 5.

Beispiel: Reale Anwendungen der Rekursion in realen Problemen

Rekursion ist eine leistungsstarke Technik, die in der Informatik und Programmierung viele Anwendungen findet. Hier sind einige der häufigsten Anwendungen der Rekursion:

Durchquerung von Bäumen und Diagrammen: Rekursion wird häufig zum Durchlaufen und Durchsuchen von Datenstrukturen wie Bäumen und Diagrammen verwendet. Rekursive Algorithmen können verwendet werden, um alle Knoten oder Eckpunkte eines Baums oder Diagramms systematisch zu untersuchen. Sortieralgorithmen: Rekursive Algorithmen werden auch in Sortieralgorithmen wie Quicksort und Merge Sort verwendet. Diese Algorithmen verwenden Rekursion, um die Daten in kleinere Unterarrays oder Unterlisten aufzuteilen, sie zu sortieren und sie dann wieder zusammenzuführen. Divide-and-Conquer-Algorithmen: Viele Algorithmen, die einen Divide-and-Conquer-Ansatz verwenden, wie z. B. der binäre Suchalgorithmus, verwenden Rekursion, um das Problem in kleinere Teilprobleme zu zerlegen. Fraktale Generierung: Fraktale Formen und Muster können mithilfe rekursiver Algorithmen generiert werden. Beispielsweise wird die Mandelbrot-Menge durch wiederholtes Anwenden einer rekursiven Formel auf komplexe Zahlen erzeugt. Backtracking-Algorithmen: Backtracking-Algorithmen werden verwendet, um Probleme zu lösen, bei denen eine Folge von Entscheidungen getroffen werden muss, wobei jede Entscheidung von den vorherigen abhängt. Diese Algorithmen können mithilfe der Rekursion implementiert werden, um alle möglichen Pfade zu erkunden und zurückzuverfolgen, wenn keine Lösung gefunden wird. Memoisierung: Memoisierung ist eine Technik, bei der die Ergebnisse teurer Funktionsaufrufe gespeichert und das zwischengespeicherte Ergebnis zurückgegeben werden, wenn dieselben Eingaben erneut auftreten. Die Memoisierung kann mithilfe rekursiver Funktionen implementiert werden, um die Ergebnisse von Teilproblemen zu berechnen und zwischenzuspeichern.

Dies sind nur einige Beispiele für die vielen Anwendungen der Rekursion in der Informatik und Programmierung. Rekursion ist ein vielseitiges und leistungsstarkes Werkzeug, mit dem viele verschiedene Arten von Problemen gelöst werden können.

Erklärung: ein echtes Beispiel für Rekursion:

Rekursion ist eine Programmiertechnik, bei der eine Funktion sich selbst aufruft. Es kann ein leistungsstarkes Werkzeug zur Lösung komplexer Probleme sein, erfordert jedoch auch eine sorgfältige Implementierung, um Endlosschleifen und Stapelüberläufe zu vermeiden.

Hier ist ein Beispiel für die Implementierung der Rekursion in Python:

C++

>

>

Java

>

>

Python3

>

>

C#

>

>

Javascript

>

>

120>

In diesem Beispiel definieren wir eine Funktion namens „Fakultät“, die eine Ganzzahl n als Eingabe akzeptiert. Die Funktion verwendet Rekursion, um die Fakultät von n zu berechnen (d. h. das Produkt aller positiven ganzen Zahlen bis zu n).

Die Fakultätsfunktion prüft zunächst, ob n 0 oder 1 ist, was die Basisfälle sind. Wenn n 0 oder 1 ist, gibt die Funktion 1 zurück, da 0! und 1! sind beide 1.

Wenn n größer als 1 ist, tritt die Funktion in den rekursiven Fall ein. Es ruft sich selbst mit n-1 als Argument auf und multipliziert das Ergebnis mit n. Dies berechnet n! durch rekursive Berechnung von (n-1)!.

Es ist wichtig zu beachten, dass die Rekursion ineffizient sein und zu Stapelüberläufen führen kann, wenn sie nicht sorgfältig eingesetzt wird. Jeder Funktionsaufruf fügt dem Aufrufstapel einen neuen Frame hinzu, was dazu führen kann, dass der Stapel zu groß wird, wenn die Rekursion zu tief ist. Darüber hinaus kann die Rekursion das Verständnis und das Debuggen des Codes erschweren, da sie das Nachdenken über mehrere Ebenen von Funktionsaufrufen erfordert.

Rekursion kann jedoch auch ein leistungsstarkes Werkzeug zur Lösung komplexer Probleme sein, insbesondere wenn ein Problem in kleinere Teilprobleme zerlegt wird. Bei richtiger Anwendung kann die Rekursion den Code eleganter und leichter lesbar machen.

Java-Listenzeichenfolge

Was sind die Nachteile der rekursiven Programmierung gegenüber der iterativen Programmierung?
Beachten Sie, dass sowohl rekursive als auch iterative Programme die gleichen Fähigkeiten zur Problemlösung haben, d. h. jedes rekursive Programm kann iterativ geschrieben werden und umgekehrt gilt dies auch. Das rekursive Programm hat einen größeren Platzbedarf als das iterative Programm, da alle Funktionen im Stapel verbleiben, bis der Basisfall erreicht ist. Aufgrund des Mehraufwands für Funktionsaufrufe und Rückgaben ist auch der Zeitbedarf höher.

Darüber hinaus sind die Codes aufgrund der geringeren Länge des Codes schwer zu verstehen und daher muss beim Schreiben des Codes besondere Sorgfalt walten. Wenn die rekursiven Aufrufe nicht ordnungsgemäß überprüft werden, kann es sein, dass der Computer nicht mehr über genügend Arbeitsspeicher verfügt.

Was sind die Vorteile der rekursiven Programmierung gegenüber der iterativen Programmierung?
Rekursion bietet eine saubere und einfache Möglichkeit, Code zu schreiben. Einige Probleme sind von Natur aus rekursiv, z. B. Baumdurchquerungen. Turm von Hanoi usw. Für solche Probleme empfiehlt es sich, rekursiven Code zu schreiben. Mit Hilfe einer Stack-Datenstruktur können wir solche Codes auch iterativ schreiben. Siehe zum Beispiel Inorder Tree Traversal without Recursion, Iterative Tower of Hanoi.

Zusammenfassung der Rekursion:

• Bei der Rekursion gibt es zwei Arten von Fällen, nämlich den rekursiven Fall und einen Basisfall.
• Der Basisfall wird verwendet, um die rekursive Funktion zu beenden, wenn sich herausstellt, dass der Fall wahr ist.
• Jeder rekursive Aufruf erstellt eine neue Kopie dieser Methode im Stapelspeicher.
• Eine unendliche Rekursion kann dazu führen, dass der Stapelspeicher knapp wird.
• Beispiele für rekursive Algorithmen: Merge Sort, Quick Sort, Tower of Hanoi, Fibonacci Series, Factorial Problem usw.

Ausgabebasierte Übungsaufgaben für Anfänger:
Übungsfragen zur Rekursion | Set 1
Übungsfragen zur Rekursion | Satz 2
Übungsfragen zur Rekursion | Satz 3
Übungsfragen zur Rekursion | Satz 4
Übungsfragen zur Rekursion | Satz 5
Übungsfragen zur Rekursion | Satz 6
Übungsfragen zur Rekursion | Satz 7
Quiz zur Rekursion
Codierungspraxis zur Rekursion:
Alle Artikel zur Rekursion
Rekursive Übungsprobleme mit Lösungen