Wie man Java für Schleifen in Rekursion umwandelt? [geschlossen] - Java, Schleifen

Ich habe drei for-Schleifen, und ich möchte sie drehenin rekursive Methode, weil ich dies für jede Menge von for-Schleifen tun möchte. Ich habe online gesucht, aber niemand scheint genau das zu haben, was ich brauche, zum Beispiel verwandelt dieser Typ Rekursion in for-Schleifen Eine rekursive Funktion in eine for-Schleife umwandeln? Code:

    int x = 3;
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
for (int k = 0; k < x; k++){
list.add(array[i] + array[j] + array[k]);
}
}
}

Antworten:

2 für die Antwort № 1

Denk an a for Schleife als eine kleine anonyme Funktion, die dauertder Schleifenindexwert als Parameter Um die nächste Iteration der Schleife zu starten, kann die Funktion einen Aufruf an sich selbst mit einem neuen Wert für den Schleifenindexparameter zurückgeben.

So was:

Object loop(int i, Object data) {
if (i > 0) {
return loop(i - 1, evolve(data));
} else {
return data;
}
}

Das ist das gleiche wie das:

for ( ; i > 0; i--) {
data = evolve(data);
}

In einigen Sprachen, insbesondere in Scheme, und wer vielleicht Java 8 oder 9 kennt, kompiliert der Compiler garantiert eine rekursive Funktion wie die Funktion loop oben genauso, wie es das zusammensetzt for Schleife oben.

In anderen Sprachen, einschließlich der aktuellen undfrüheren Versionen von Java werden fast alle Compiler eine ausführbare Datei erstellen, die einen großen Call-Stack erstellt. Wenn der Aufrufstapel groß ist, kann er sogar die zulässige Größe überschreiten und das Programm zum Absturz bringen.


2 für die Antwort № 2

Hasser beiseite, lass uns das tun! [1]

Gegeben:

int x = 3;
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
for (int k = 0; k < x; k++){
list.add(array[i] + array[j] + array[k]);
}
}
}

Denken wir darüber nach jede Schleife ist es eine eigene rekursive Funktion - wie dies machtdie Wiederholungsfälle viel einfacher! Dies ist auch die einzige "nicht-denkende" Methode, die ich kenne, um die Schleifen in Rekursion zu verwandeln. Die rekursive Tiefe ist begrenzt auf 3*x => i+j+k es ist also ziemlich sicher für einen kleinen[2] x.

In Java wird für jede Schleife eine separate Methode benötigt, um diese Struktur zu codieren. (In einer Sprache mit Funktionen höherer Ordnung könnten diese drei Funktionen abstrakt kombiniert werden, aber nicht in Java [7].)

void loopI(int i) {
if (i < x) {
loopJ(0);   // "start j loop"
loopI(i++); // "next i loop" / recurrence case
}
// "end loop" / base case
}

void loopJ(int j) {
if (j < x) {
loopK(0);
loopJ(j++);
}
}

void loopK(int k) {
if (k < x) {
list.add(array[i] + array[j] + array[k]);
loopK(k++);
}
}

// do it!
loopI(0);

Alle von denen könnte zu einer einzigen rekursiven Funktion kombiniert werden, aberDas macht die Behandlung der Wiederholungsfälle ein bisschen schwieriger, da "Denken" und zusätzliche Bedingungen (oder Mod-Ausdrücke, vielleicht) erforderlich sind, um den Zustand voranzutreiben.

Hier ist ein Beispiel für eine kombiniert rekursive Funktion (das ist falsch wenn x ist 0). Im Gegensatz zu dem obigen Ansatz mit drei Methoden wird die Stapeltiefe zu wachsen x^3 => i*j*k. Dies wird Java's Rekursionslimits leicht töten - auch für kleinere Werte von x- als Java [7] tut nicht haben Tail-Call-Optimierung.

void loop(int i, int j, int k) {
list.add(array[i] + array[j] + array[k]);

// advance states
k++;
if (k == x) { k = 0; j++; }
if (j == x) { j = 0; i++; }
if (i == x) { i = 0; }

// terminate on all wrap-around
if (i == 0 && j == 0 && k == 0) { return; }

// recurse
loop(i, j, k);
}

[1] YMMV, nur für theoretische Zwecke - Ich liebe Rekursion, aber es ist nicht geeignet für dieser Fall in Java.

[2] Für etwas Wert von "klein". Sehen Sie, wie tief Ihr Stack gehen kann!


Speisekarte