Was sind die Vor- und Nachteile der Rekursion?

Rekursion bedeutet, dass eine Funktion wiederholt aufgerufen wird

Es verwendet den Systemstack, um seine Aufgabe zu erfüllen. Wenn der Stack den Ansatz LIFO verwendet Wenn eine Funktion aufgerufen wird, wird der Controller an die Stelle verschoben, an der die Funktion definiert ist, die mit einer bestimmten Adresse im Speicher abgelegt ist. Diese Adresse wird im Stack gespeichert

Zweitens reduziert es die zeitliche Komplexität eines Programms. 

Obwohl etwas abseits, ein bisschen verwandt. Muss lesen. : Rekursion gegen Iteration

Alle Algorithmen können rekursiv definiert werden. Das macht es viel einfacher zu visualisieren und zu beweisen. 

Einige Algorithmen (z. B. die Ackermann-Funktion ) können nicht (leicht) iterativ angegeben werden. 

Eine rekursive Implementierung belegt mehr Speicher als eine Schleife, wenn die Optimierung von tail call nicht ausgeführt werden kann. Zwar benötigt die Iteration möglicherweise weniger Speicher als eine rekursive Funktion, die nicht optimiert werden kann, ihre Ausdruckskraft ist jedoch eingeschränkt.

Ich persönlich bevorzuge die Verwendung der iterativen Funktion der rekursiven Funktion. Besonders wenn Ihre Funktion eine komplexe/schwere Logik hat und die Anzahl der Iterationen groß ist. Dies liegt daran, dass bei jedem rekursiven Aufruf der Call Stack zunimmt. Es kann zu einem Absturz des Stapels kommen, wenn die Vorgänge zu groß sind und der Prozess verlangsamt.

Jeder Algorithmus, der mit Rekursion implementiert wird, kann auch durch Iteration implementiert werden.

Warum nicht Rekursion verwenden

1. Normalerweise ist es langsamer, da der Stapel überflüssig ist.
2. Normalerweise wird mehr Speicher für den Stack benötigt.

Warum zur Rekursion verwenden

1. Rekursion fügt Klarheit hinzu und verringert (manchmal) die Zeit, die zum Schreiben und Debuggen von Code benötigt wird (reduziert jedoch nicht unbedingt den Speicherplatz oder die Ausführungsgeschwindigkeit).
2. Reduziert die zeitliche Komplexität.
3. Bessere Leistung bei der Lösung von Problemen basierend auf Baumstrukturen.

Beispielsweise wird das Problem des Turms von Hanoi leichter durch Rekursion als durch Iteration gelöst.

Anfangen:

Pros:

• Dies ist die einzigartige Art, eine variable Anzahl von geschachtelten Schleifen zu implementieren (und die einzige elegante Art, eine große konstante Anzahl von geschachtelten Schleifen zu implementieren).

Nachteile:

• Rekursive Methoden lösen bei der Verarbeitung großer Mengen häufig eine StackOverflowException aus. Rekursive Schleifen haben dieses Problem jedoch nicht.

Ausdruckskraft

Die meisten Probleme äußern sich natürlich in Rekursionen wie Fibonacci, Merge-Sortierung und schnelle Sortierung. In dieser Hinsicht ist der Code für Menschen geschrieben, nicht für Maschinen. 

Unveränderlichkeit

Iterative Lösungen sind häufig auf unterschiedliche temporäre Variablen angewiesen, wodurch der Code schwer lesbar wird. Dies kann mit Rekursion vermieden werden.

Performance

Rekursion ist nicht stapelfreundlich. Der Stapel kann überlaufen, wenn die Rekursion nicht gut ausgelegt ist oder die Optimierung des Abschnitts nicht unterstützt wird.

In einer Situation könnte es vorkommen, dass Sie die Rekursion in einem Problem aufgeben müssen, bei dem die Rekursion zu Ihrem Vorteil zu sein scheint. Dies liegt daran, dass bei Problemen, bei denen die Rekursion tausendmal auftreten müsste, dies zu einem stackoverflow-Fehler führen würde, obwohl Ihr Code dies tat nicht in einer unendlichen rekursion stecken. In den meisten Programmiersprachen sind Sie auf eine Reihe von Stackaufrufen beschränkt. Wenn Ihre Rekursion diese Grenze überschreitet, sollten Sie die Rekursion möglicherweise nicht verwenden.

Wir sollten Rekursion in folgenden Szenarien verwenden:

• wenn wir die endliche Anzahl von Iterationen nicht kennen, basiert unsere Funktionsausstiegsbedingung auf der dynamischen Programmierung (Memoization).
• wenn wir Operationen in umgekehrter Reihenfolge der Elemente durchführen müssen. Das heißt, wir wollen das letzte Element zuerst und dann n-1, n-2 usw. bis zum ersten Element verarbeiten

Rekursion speichert mehrere Durchgänge. Und es wird nützlich sein, wenn wir die Stapelzuordnung wie folgt teilen können:

int N = 10;
int output = process(N) + process(N/2);
public void process(int n) {
    if (n==N/2 + 1 || n==1) {
       return 1;
    }

    return process(n-1) + process(n-2);
}

In diesem Fall werden zu jeder Zeit nur halbe Stapel zugewiesen.