Detaillierte Erläuterung von Iterations- und Rekursionsbeispielen in Java

Dieser Artikel führt Sie hauptsächlich in die Iteration und die Rekursion in Java ein Der damit verbundene Inhalt der Zahlenform-Rekursion wird im Artikel ausführlich vorgestellt. Ich glaube, dass er für alle, die ihn studieren, einen gewissen Referenzwert haben wird. Vorwort

Ich habe diesen Inhalt kürzlich beim Lesen eines Buches gesehen und empfand ihn als recht lohnend. Die Iteration verwendet Schleifen (for, while, do...wile) oder Iteratoren und wird beendet, wenn die Schleifenbedingungen nicht erfüllt sind. Rekursion, im Allgemeinen Funktionsrekursion, kann sich selbst aufrufen oder ein indirekter Aufruf sein, dh Methode A ruft Methode B auf und Methode B ruft wiederum Methode A auf. Die Bedingungen für den rekursiven Ausgang sind if, else-Anweisung , beenden, wenn die Bedingung die Basis erfüllt.

Das Obige sind die grammatikalischen Merkmale von Iteration und Rekursion. Was sind ihre Unterschiede in Java? Erfahren Sie mehr darüber in diesem Artikel unten.

1. Rekursion

Wenn es um Iteration geht, muss ich einen mathematischen Ausdruck erwähnen:

Es gibt viele Möglichkeiten, die Fakultät zu berechnen. Jeder mit einem bestimmten mathematischen Fundament weiß Daher kann die Implementierung des Codes direkt geschrieben werden: n!=n*(n-1)*(n-2)*...*1

Code 1

n!=n*(n-1)!

Bei der Ausführung des obigen Codes muss die Maschine dies tatsächlich tun Führen Sie für die Reihenmultiplikation Folgendes aus:

→

→

int factorial (int n) {
 if (n == 1) {
  return 1;
 } else {
  return n*factorial(n-1);
 }
}

→ … →

. Daher ist es notwendig, die Multiplikation kontinuierlich zu verfolgen (das Ergebnis der letzten Berechnung zu verfolgen) und zur Berechnung aufzurufen (eine Multiplikationskette aufzubauen). Diese Art von Operation, die sich kontinuierlich selbst aufruft, wird Rekursion genannt. Die Rekursion kann weiter in lineare Rekursion und numerische Rekursion unterteilt werden. Eine Rekursion, bei der die Informationsmenge linear mit der Eingabe des Algorithmus zunimmt, wird als lineare Rekursion bezeichnet. Die Berechnung von n! (Fakultät) ist eine lineare Rekursion. Denn mit zunehmendem N nimmt die für die Berechnung benötigte Zeit linear zu. Eine andere Art von Informationen, die mit zunehmender Eingabe exponentiell zunimmt, wird als Baumrekursion bezeichnet. factorial(n) factorial(n-1) factorial(n-2) factorial(1) 2. Iteration

Eine andere Möglichkeit, n zu berechnen, ist: Zuerst 1 mit 2 multiplizieren und dann das Ergebnis mit 3 multiplizieren Multiplizieren Sie das erhaltene Ergebnis mit 4... und multiplizieren Sie es bis N. Bei der Implementierung des Programms können Sie einen Zähler definieren. Bei jeder Multiplikation wird der Zähler erhöht, bis der Zählerwert gleich N ist. Der Code lautet wie folgt: Code 2

Im Vergleich zu Code 1 erstellt Code 2 keine Multiplikationskette. Bei der Durchführung jedes Berechnungsschritts müssen Sie lediglich das aktuelle Ergebnis (Produkt) und den Wert von i kennen. Diese Berechnungsform nennt man Iteration. Es gibt mehrere Bedingungen für die Iteration: 1. Es gibt eine

Variable

mit einem Anfangswert. 2. Eine Regel, die beschreibt, wie Variablenwerte aktualisiert werden. 3. Eine Endbedingung. (Drei Elemente einer Schleife: Schleifenvariablen, Schleifenkörper und Schleifenabschlussbedingung). Identisch mit Rekursion. Zeitanforderungen, die linear mit der Eingabe wachsen, können als lineare Iterationen bezeichnet werden.

int factorial (int n) {
 int product = 1;
 for(int i=2; i<n; i++) {
  product *= i;
 }
 return product;
}

3. Iteration VS Rekursion

Beim Vergleich der beiden Programme können wir feststellen, dass sie fast gleich aussehen, insbesondere hinsichtlich ihrer mathematischen Funktionen. Bei der Berechnung von n! ist ihre Anzahl der Berechnungsschritte proportional zum Wert von n. Betrachtet man jedoch ihre Funktionsweise aus der Perspektive des Programms, dann sind die beiden Algorithmen sehr unterschiedlich. (Hinweis: Der Originalartikel ist etwas albern in Bezug auf den Unterschied, daher werde ich ihn hier nicht übersetzen. Das Folgende ist die eigene Zusammenfassung des Autors.)

Analysieren Sie zunächst die Rekursion Der größte Vorteil der Rekursion besteht darin, dass ein komplexer Algorithmus in eine Reihe identischer wiederholbarer Schritte zerlegt wird. Daher erfordert die Verwendung von Rekursion zur Implementierung einer Berechnungslogik oft nur einen kurzen Code zum Lösen, und dieser Code ist relativ einfach zu verstehen. Rekursion bedeutet jedoch viele Funktionsaufrufe. Der Grund, warum der lokale Status von Funktionsaufrufen mithilfe des Stapels aufgezeichnet wird. Daher kann dies viel Platz verschwenden und zu einem Stapelüberlauf führen, wenn die Rekursion zu tief ist.

Analysieren Sie als Nächstes die Iterationen. Tatsächlich kann die Rekursion durch Iteration ersetzt werden. Aber im Vergleich zur Rekursion, die einfach und leicht zu verstehen ist, ist die Iteration stumpfer und schwieriger zu verstehen. Vor allem, wenn es um eine komplexere Szene geht. Allerdings liegen auch die Nachteile, die das schwierige Verständnis des Codes mit sich bringt, auf der Hand. Die Iteration ist effizienter als die Rekursion und verbraucht weniger Platz.

Es muss eine Iteration in der Rekursion geben, aber möglicherweise keine Rekursion in der Iteration, und die meisten davon können ineinander umgewandelt werden.

Verwenden Sie keine Rekursion, wenn eine Iteration möglich ist. Rekursive Aufruffunktionen verschwenden nicht nur Platz, sondern verursachen auch leicht einen Stapelüberlauf, wenn die Rekursion zu tief ist.

4. Zahlenrekursion

前面介绍过，树递归随输入的增长的信息量呈指数级增长。比较典型的就是斐波那契数列：

用文字描述就是斐波那契数列中前两个数字的和等于第三个数字：0,1,1,2,3,5,8,13,21……

递归实现代码如下：

int fib (int n) {
 if (n == 0) {
  return 0;
 } else if (n == 1) {
  return 1;
 } else {
  return fib(n-1) + fib(n-2);
 }
}

计算过程中，为了计算fib(5) ，程序要先计算fib(4) 和 fib(3) ，要想计算fib(4) ，程序同样需要先计算 fib(3) 和 fib(2) 。在这个过程中计算了两次fib(3)。

从上面分析的计算过程可以得出一个结论：使用递归实现斐波那契数列存在冗余计算。

就像上面提到的，可以用递归的算法一般都能用迭代实现，斐波那契数列的计算也一样。

int fib (int n) {
 int fib = 0;
 int a = 1;
 for(int i=0; i<n; i++) {
  int temp = fib;
  fib = fib + a;
  a = temp;
 }
 return fib;
}

虽然使用递归的方式会有冗余计算，可以用迭代来代替。但是这并不表明递归可以完全被取代。因为递归有更好的可读性。

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung von Iterations- und Rekursionsbeispielen in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!