Empfohlen, 2019

Tipp Der Redaktion

Unterschied zwischen Rekursion und Iteration

Rekursion und Iteration führen den Befehlssatz wiederholt aus. Rekursion ist, wenn eine Anweisung in einer Funktion sich wiederholt aufruft. Die Iteration ist, wenn eine Schleife wiederholt ausgeführt wird, bis die Steuerungsbedingung falsch wird. Der Hauptunterschied zwischen Rekursion und Iteration besteht darin, dass eine Rekursion ein Prozess ist, der immer auf eine Funktion angewendet wird. Die Iteration wird auf den Satz von Anweisungen angewendet, die wiederholt ausgeführt werden sollen.

Vergleichstabelle

Basis zum VergleichRekursionIteration
BasicDie Anweisung in einem Funktionskörper ruft die Funktion selbst auf.Ermöglicht die wiederholte Ausführung des Befehlssatzes.
FormatBei der rekursiven Funktion wird nur die Beendigungsbedingung (Basisfall) angegeben.Die Iteration umfasst Initialisierung, Bedingung, Ausführung der Anweisung innerhalb einer Schleife und Aktualisierung (Inkrementieren und Dekrementieren) der Steuervariablen.
BeendigungEine bedingte Anweisung ist im Rumpf der Funktion enthalten, um die Rückkehr der Funktion zu erzwingen, ohne dass ein Rekursionsaufruf ausgeführt wird.Die Iterationsanweisung wird wiederholt ausgeführt, bis eine bestimmte Bedingung erreicht ist.
BedingungWenn die Funktion nicht zu einer bestimmten Bedingung (Basisfall) konvergiert, führt dies zu einer unendlichen Rekursion.Wenn die Steuerungsbedingung in der Iterationsanweisung niemals falsch wird, führt dies zu einer unendlichen Iteration.
Unendliche WiederholungUnendliche Rekursion kann das System zum Absturz bringen.Endlosschleife verwendet wiederholt CPU-Zyklen.
AngewendetRekursion wird immer auf Funktionen angewendet.Iteration wird auf Iterationsanweisungen oder "Schleifen" angewendet.
StapelDer Stack wird verwendet, um die neuen lokalen Variablen und Parameter bei jedem Aufruf der Funktion zu speichern.Verwendet keinen Stack.
OverheadRekursion hat den Aufwand von wiederholten Funktionsaufrufen.Kein Aufwand für wiederholten Funktionsaufruf.
GeschwindigkeitLangsame AusführungSchnell in der Ausführung.
Größe des CodesRekursion reduziert die Größe des Codes.Durch Iteration wird der Code länger.

Definition von Rekursion

C ++ erlaubt es einer Funktion, sich innerhalb ihres Codes aufzurufen. Das heißt, die Definition der Funktion besitzt einen Funktionsaufruf für sich. Manchmal wird es auch als „ zirkuläre Definition “ bezeichnet. Die von der Funktion verwendeten lokalen Variablen und Parameter werden bei jedem Aufruf der Funktion neu erstellt und oben im Stack gespeichert. Bei jedem Aufruf einer Funktion wird jedoch keine neue Kopie dieser Funktion erstellt. Die rekursive Funktion reduziert die Größe des Codes nicht wesentlich und verbessert die Speicherauslastung nicht einmal, im Vergleich zur Iteration jedoch etwas.

Um die Rekursion zu beenden, müssen Sie eine select-Anweisung in die Definition der Funktion einschließen, um die Rückkehr der Funktion zu erzwingen, ohne einen rekursiven Aufruf an sich selbst vorzunehmen. Das Fehlen der select-Anweisung in der Definition einer rekursiven Funktion lässt die Funktion bei der unendlichen Rekursion einmal aufgerufen werden.

Lassen Sie uns die Rekursion mit einer Funktion verstehen, die die Fakultät der Zahl zurückgibt.

 int Fakultät (int num) {int Antwort; if (num == 1) {return 1; } else {Antwort = Fakultät (num-1) * num; // rekursives Aufrufen} return (Antwort); } 

Im obigen Code zeigt die Anweisung im else-Teil die Rekursion, da die Anweisung die Funktion factorial () aufruft, in der sie sich befindet.

Definition von Iteration

Iteration ist ein Prozess, bei dem der Befehlssatz wiederholt ausgeführt wird, bis die Bedingung in der Iterationsanweisung falsch wird. Die Iterationsanweisung umfasst die Initialisierung, den Vergleich, die Ausführung der Anweisungen innerhalb der Iterationsanweisung und schließlich die Aktualisierung der Steuervariablen. Nachdem die Steuervariable aktualisiert wurde, wird sie erneut verglichen und der Prozess wiederholt sich selbst, bis sich die Bedingung in der Iterationsanweisung als falsch herausstellt. Die Iterationsanweisungen lauten "for" -Schleife, "while" -Schleife, "do-while" -Schleife.

Die Iterationsanweisung verwendet keinen Stapel zum Speichern der Variablen. Daher ist die Ausführung der Iterationsanweisung im Vergleich zur rekursiven Funktion schneller. Sogar die Iterationsfunktion hat nicht den Aufwand eines wiederholten Funktionsaufrufs, der auch die Ausführung schneller als die rekursive Funktion macht. Die Iteration wird beendet, wenn die Steuerbedingung falsch wird. Das Fehlen einer Steuerungsbedingung in der Iterationsanweisung kann zu einer Endlosschleife oder zu einem Kompilierungsfehler führen.

Verstehen wir die Iteration bezüglich des obigen Beispiels.

 int Fakultät (int num) {int answer = 1; // muss initialisiert werden, da er vor der Initialisierung für (int t = 1; t> num; t ++) einen Abfallwert enthalten kann // Iteration {answer = answer * (t); Rückkehr (Antwort); }} 

Im obigen Code gibt die Funktion die Fakultät der Zahl mithilfe der Iterationsanweisung zurück.

Hauptunterschiede zwischen Rekursion und Iteration

  1. Rekursion ist, wenn eine Methode in einem Programm wiederholt sich selbst aufruft, während Iteration ist, wenn ein Satz von Anweisungen in einem Programm wiederholt ausgeführt wird.
  2. Eine rekursive Methode enthält eine Menge von Anweisungen, eine Anweisung, die sich selbst aufruft, und eine Beendigungsbedingung, während Iterationsanweisungen Initialisierung, Inkrement, Bedingung, Befehlssatz innerhalb einer Schleife und eine Steuervariable enthalten.
  3. Eine bedingte Anweisung entscheidet über die Beendigung des Rekursionswerts, und der Wert der Kontrollvariablen entscheidet über die Beendigung der Iterationsanweisung.
  4. Wenn die Methode nicht zur Beendigungsbedingung führt, tritt sie in unendliche Rekursion ein. Wenn dagegen die Steuervariable niemals zum Beendigungswert führt, wiederholt sich die Iterationsanweisung unendlich oft.
  5. Eine unendliche Rekursion kann zu einem Systemabsturz führen, während eine unendliche Iteration CPU-Zyklen beansprucht.
  6. Die Rekursion wird immer auf die Methode angewendet, während die Iteration auf den Befehlssatz angewendet wird.
  7. Während der Rekursion erstellte Variablen werden im Stapel gespeichert, während für die Iteration kein Stapel erforderlich ist.
  8. Rekursion verursacht den Overhead von wiederholten Funktionsaufrufen, während Iteration keine Funktion hat, die Overhead aufruft.
  9. Aufgrund des Funktionsaufrufs ist die Ausführung der Rekursion langsamer, während die Ausführung der Iteration schneller ist.
  10. Rekursion reduziert die Größe des Codes, während Iterationen einen Code länger machen.

Fazit:

Die rekursive Funktion ist leicht zu schreiben, aber sie ist im Vergleich zur Iteration nicht gut, während die Iteration schwer zu schreiben ist, aber ihre Leistung ist im Vergleich zur Rekursion gut.

Top