Rekursion:
In Programmierbegriffen kann eine rekursive Funktion als eine Routine definiert werden, die sich direkt oder indirekt aufruft.
Mit rekursiven Algorithmus können bestimmte Probleme ganz einfach gelöst werden. Türme von Hanoi (TOH) ist eine solche Programmierung. Versuchen Sie, einen iterativen Algorithmus für TOH zu schreiben. Darüber hinaus kann jedes rekursive Programm mit iterativen Methoden geschrieben werden (Siehe Datenstrukturen von Lipschutz).
Mathematisch Rekursion hilft, einige Rätsel leicht zu lösen.,
Zum Beispiel eine Routine-Interview Frage,
In einer Gruppe von N Personen, wird jede Person ihre/seine Hand mit jeder anderen Person nur einmal schütteln. Auf insgesamt wie viele hand-shakes, würde passieren?
Lösung:
Es kann auf verschiedene Arten gelöst werden, Graphen,Rekursion usw. Mal sehen, wie rekursiv es gelöst werden kann.
Es gibt N Personen. Jede Person schütteln-Hand mit einander nur einmal. In Anbetracht N-ten person, (s)er hat zu schütteln-hand mit (N-1) personen. Jetzt reduzierte sich das Problem auf eine kleine Instanz von (N-1) Personen. Unter der Annahme von TN als totaler Handschlag kann es rekursiv formuliert werden.,
TN = (N-1) + TN-1
Wenn Sie es rekursiv lösen, ergibt sich eine arithmetische Reihe, die zu N (N-1)/2 ausgewertet werden kann.
Übung: In einer Gruppe von N Paaren kann nur ein Geschlecht (entweder männlich oder weiblich) mit jedem die Hand schütteln. Wie viele Händeschütteln würden passieren?
In der Regel rekursive Programme führt zu einer schlechten Zeit Komplexität. Ein Beispiel ist die Fibonacci-Reihe. Die zeitliche Komplexität der Berechnung der n-ten Fibonacci-Zahl mithilfe der Rekursion beträgt ungefähr 1,6 n. Dies bedeutet, dass derselbe Computer fast 60% mehr Zeit für die nächste Fibonacci-Zahl benötigt. Der rekursive Fibonacci-Algorithmus hat Unterprobleme überlappt., Es gibt andere Techniken wie dynamische Programmierung, um solche überlappenden Algorithmen zu verbessern.
Einige Algorithmen (z. B. Merge sort, Quick sort, etc…) führen jedoch zu einer optimalen Zeitkomplexität durch Rekursion.
Basisfall:
Eine kritische Anforderung rekursiver Funktionen ist der Beendigungspunkt oder Basisfall. Jedes rekursive Programm muss über einen Basisfall verfügen, um sicherzustellen, dass die Funktion beendet wird. Fehlender Basisfall führt zu unerwartetem Verhalten.,
Verschiedene Möglichkeiten, rekursive Funktionen zu schreiben
Funktionsaufruf selbst: (Direkter Weg)
Die meisten von uns kennen atleast zwei verschiedene Möglichkeiten, rekursive Programme zu schreiben. Da unten ist Türme von Hanoi-code. Es ist ein Beispiel für direktes Anrufen.

Ausgabe:

Move the disk 1 from S to DMove the disk 2 from S to AMove the disk 1 from D to AMove the disk 3 from S to DMove the disk 1 from A to SMove the disk 2 from A to DMove the disk 1 from S to D

Die Zeitkomplexität von TOH kann durch die Formulierung der Anzahl der Züge berechnet werden.
Wir müssen die ersten N-1-Platten von der Quelle in die Hilfs-und von Hilfs-zum Ziel verschieben, dh die ersten N-1-Platten erfordern zwei Züge. Eine weitere Verschiebung der letzten Festplatte von der Quelle zum Ziel., Mathematisch kann es rekursiv definiert werden.
MN = 2MN-1 + 1.
Wir können die obige rekursive Beziehung (2N-1), die exponentiell ist, leicht lösen.
Rekursion mit gegenseitigen Funktionsaufruf: (Indirekte Weise)
Indirekter Aufruf. Obwohl am wenigsten praktisch, kann eine Funktion eine andere Funktion aufrufen, die inturn frühere Funktion aufruft. In diesem Fall sollten beide Funktionen den Basisfall haben.
Defensive Programmierung:
Wir können defensive Codierungstechniken mit Rekursion für anmutige Funktionalität der Anwendung kombinieren., Normalerweise ist rekursive Programmierung in sicherheitskritischen Anwendungen wie Flugkontrollen, Gesundheitsüberwachung usw. nicht zulässig. Man kann jedoch eine statische Zähltechnik verwenden, um unkontrollierte Aufrufe zu vermeiden (NICHT in sicherheitskritischen Systemen, kann in weichen Echtzeitsystemen verwendet werden).

Die callDepth-Tiefe hängt von der Größe des Funktionsstapelrahmens und der maximalen Stapelgröße ab.
Rekursion mit Funktionszeigern: (Indirekte Weise)
Rekursion kann auch mit Funktionszeigern implementiert. Ein Beispiel ist der Signalhandler in POSIX-Beschwerdesystemen., Wenn der Handler bewirkt, dass dasselbe Ereignis ausgelöst wird, aufgrund dessen der Handler aufgerufen wird, wird die Funktion erneut gestartet.