Vorwort
Ich habe diesen Inhalt kürzlich gesehen, als ich ein Buch gelesen habe und fühlte mich ziemlich lohnend. Iteration verwendet eine Schleife (für, während, do ... wile) oder einen Iterator, der ausgeht, wenn der Schleifenbedingung nicht erfüllt ist. Rekursion ist im Allgemeinen eine Funktionsrekursion, die von sich selbst oder durch nicht gerichtete Aufrufe genannt werden kann, dh Methode A-Aufrufmethode B und Methode B-Aufrufmethode A wiederum und die Bedingung für den rekursiven Ausgang ist eine IF-Anweisung, und beendet, wenn die Bedingung die Grundlage erfüllt.
Die oben genannten sind die Syntaxeigenschaften von Iteration und Rekursion. Was sind die Unterschiede zwischen ihnen in Java? Erfahren wir weiter unten mehr über diesen Artikel.
1. Rekursion
Wenn es um Iteration geht, müssen wir einen mathematischen Ausdruck erwähnen: n!=n*(n-1)*(n-2)*...*1
Es gibt viele Möglichkeiten, Faktorien zu berechnen. Jeder mit einem bestimmten mathematischen Fundament kennt n!=n*(n-1)! Daher kann die Code -Implementierung direkt geschrieben werden wie:
Code 1
int factorial (int n) {if (n == 1) {return 1; } else {return n*factorial (n-1); }} Bei der Ausführung des oben genannten Code muss der Computer tatsächlich eine Reihe von Multiplikationen ausführen: factorial(n) → factorial(n-1) → factorial(n-2) →… → factorial(1) . Daher ist es notwendig, den Überblick zu behalten (das Ergebnis der letzten Berechnung verfolgen) und die Multiplikation aufrufen, um Berechnungen durchzuführen (eine Multiplikationskette erstellen). Diese Art von Operation, die sich ständig aufruft, wird als Rekursion bezeichnet. Rekursion kann weiter in eine lineare Rekursion und numerische Rekursion unterteilt werden. Die Informationsmenge nimmt mit der Eingabe des Algorithmus linear zu. Rekursion wird als lineare Rekursion bezeichnet. Berechnen n! (Fabrik) ist eine lineare Rekursion. Da mit n zunimmt, nimmt die für die Berechnung erforderliche Zeit linear zu. Eine andere Art von Informationen, die mit der Erhöhung der Eingabe exponentiell wachsen, wird als Baumrekursion bezeichnet.
2. Iteration
Eine andere Möglichkeit, n zu berechnen! IS: Berechnen Sie zuerst 1 Multiplizieren Sie mit 2, multiplizieren Sie dann das Ergebnis mit 3 und multiplizieren Sie das Ergebnis mit 4 ... und multiplizieren Sie sie bis N. Während der Implementierung des Programms kann ein Zähler definiert werden. Jedes Mal, wenn eine Multiplikation durchgeführt wird, wird der Zähler einmal inkrementiert, bis der Wert des Zählers gleich N ist. Der Code ist wie folgt:
Code zwei
int factorial (int n) {int product = 1; für (int i = 2; i <n; i ++) {product *= i; } Return Product;}Im Vergleich zu Code eins erstellt Code Two keine Multiplikationskette. Wenn Sie jeden Berechnungsschritt ausführen, müssen Sie nur das aktuelle Ergebnis (Produkt) und die Werte von i kennen. Diese Form der Berechnung wird als Iteration bezeichnet. Es gibt mehrere Bedingungen für die Iteration: 1. Es gibt eine Variable mit einem Anfangswert. 2. Eine Regel, die erklärt, wie variable Werte aktualisiert werden. 3. Ein Endzustand. (Drei Elemente der Schleife: Schleifenvariablen, Schleifenkörper und Schleifenabschlüsse). Gleich wie Rekursion. Die zeitliche Anforderung, die linear wird, wenn der Eingang linear wächst, kann als lineare Iteration bezeichnet werden.
3. Iteration vs. Rekursion
Nach dem Vergleich der beiden Programme können wir feststellen, dass sie fast gleich aussehen, insbesondere in Bezug auf ihre mathematischen Funktionen. Bei der Berechnung von n!, Sind ihre Berechnungsschritte proportional zum Wert von n. Wenn wir jedoch die Perspektive des Programms einnehmen und überlegen, wie sie laufen, sind die beiden Algorithmen sehr unterschiedlich.
(Hinweis: Der Originaltext ist ein bisschen irrelevant über den Unterschied, daher werde ich ihn hier nicht übersetzen. Das Folgende ist die eigene Zusammenfassung des Autors.)
Analysieren Sie zunächst die Rekursion. Tatsächlich ist das Größte an der Rekursion, einen komplexen Algorithmus in mehrere identische wiederholbare Schritte zu zerlegen. Die Verwendung von Rekursion zur Implementierung einer Rechenlogik erfordert daher häufig nur einen sehr kurzen Code, um zu lösen, und ein solcher Code ist einfacher zu verstehen. Rekursion bedeutet jedoch eine große Anzahl von Funktionsaufrufen. Der Grund, warum der örtliche Zustand eines Funktionsaufrufs mit einem Stapel aufgezeichnet wird. Daher kann dies viel Platz verschwenden, und wenn die Rekursion zu tief ist, kann sie einen Stapelüberlauf verursachen.
Analysieren Sie als nächstes Iterationen. Tatsächlich kann Rekursion durch Iteration ersetzt werden. Im Vergleich zu Einfachheit und Verständnis der Rekursion ist die Iteration jedoch starrer und schwer verständlicher. Besonders bei der Begegnung mit einem komplexeren Szenario. Die Schwierigkeit, den Code zu verstehen, bringt jedoch auch offensichtliche Punkte. Die Effizienz der Iteration ist höher als die Rekursion und im Weltraumverbrauch relativ gering.
Es müssen Iterationen in der Rekursion vorhanden sein, aber es gibt möglicherweise keine Wiederholungen in Iterationen, und die meisten können zueinander umgewandelt werden.
Wenn Sie Iteration verwenden können, verwenden Sie keine Rekursion. Das Aufrufen von Funktionen verschwendet nicht nur den Raum, sondern kann auch leicht zu einem Stapelüberlauf führen, wenn die Rekursion zu tief ist.
4. Zahlenüberschreitung
Wie bereits erwähnt, nimmt die Menge an Informationen, die der Baumrevursive exponentiell erhöht, mit der Erhöhung der Eingabe zu. Die Fibonacci -Sequenz ist ein typisches Beispiel:
In der Textbeschreibung ist die Summe der ersten beiden Zahlen in der Fibonacci -Sequenz gleich der dritten Zahl: 0, 1, 1, 2, 3, 5, 8, 13, 21 ...
Der rekursive Implementierungscode lautet wie folgt:
int fib (int n) {if (n == 0) {return 0; } else if (n == 1) {return 1; } else {return fib (n-1) + fib (n-2); }} Während des Berechnungsprozesses muss das Programm zuerst fib(4) und fib(3) berechnen, um fib(5) zu berechnen. Um fib(4) zu berechnen, muss das Programm zuerst fib(3) und fib(2) berechnen. Fib (3) wird während dieses Prozesses zweimal berechnet.
Aus dem oben analysierten Berechnungsprozess können wir eine Schlussfolgerung ziehen: Es gibt eine redundante Berechnung für die Implementierung der Fibonacci -Sequenz unter Verwendung von Rekursion.
Wie oben erwähnt, können rekursive Algorithmen im Allgemeinen durch iterativ implementiert werden, und dasselbe gilt für Fibonacci -Sequenzberechnungen.
int fib (int n) {int fib = 0; int a = 1; für (int i = 0; i <n; i ++) {int temp = fib; fib = fib + a; a = temp; } return fib;}Obwohl es in der Rekursionsmethode redundante Berechnungen geben wird, kann es durch Iteration ersetzt werden. Dies bedeutet jedoch nicht, dass die Rekursion vollständig ersetzt werden kann. Weil Rekursion eine bessere Lesbarkeit hat.
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, der Inhalt dieses Artikels wird für alle beim Lernen oder der Verwendung von Java hilfreich sein. Wenn Sie Fragen haben, können Sie eine Nachricht zur Kommunikation überlassen.