Ändern einer for-Schleife in eine rekursive Funktion

Question

so habe ich gelesen, dass Sie jede Schleife in eine rekursive Funktion verwandeln können, und ich frage mich, wie ich den folgenden Code drehen könnte (druckt die Permutationen einer Zeichenfolge aus) in eins (Ersetzen der for-Schleife durch eine rekursive Funktion). Ich frage nicht nach einer Lösung, sondern nach der Art und Weise, wie man sich einer solchen Aufgabe annähert. Vielen Dank!

private static void permutation(String prefix, String str) { 

int n = str.length(); 

    if (n == 0) System.out.println(prefix); 

    else { 

    for (int i = 0; i < n; i++) 
     permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n)); 
    } 
} 

Danke allen!

Answer 1

Parameter Fügen Sie die untere und obere Grenze darstellen,

private static void permutation(String prefix, String str, int i, int j) { 

eine Randbedingung zu Beginn der Permutation hinzufügen,

if(i < j){ 

dann die for Schleife weglassen, und in Ihrem bereits rekursiven Aufruf zu Permutation,

permutation(..., i+1, j); 

und schließlich, wenn Sie Nennen Sie es zunächst von Ihrem anderen Code, übergeben Sie 0 und den Parameter str. length() als die Werte von i und j.

Sie könnten auch eine andere Permutation (...) Überladung erstellen, die die zwei zusätzlichen Parameter übernimmt, so dass Ihr erster Aufruf sie nicht herausfinden muss.

Beachten Sie, dass Sie einige der Redundanz um n in Ihrem Code entfernen können, aber Sie können dies funktioniert, ohne dies zu tun.

Answer 2

Wenn Sie den Vertrag nicht ändern möchten, tun Sie es, indem Sie einen Helfer machen.

private static void permutationFor(int i, int n, String prefix, String str) { 
    if(i < n) { 
     permutation(prefix + str.charAt(i), 
        str.substring(0, i) + str.substring(i+1, n)); 
     permutationFor(i+1, n, prefix, str); 
    } 
} 

So ändern Sie die for-Schleife mit einem Aufruf an permututaionFor

private static void permutation(String prefix, String str) { 
    int n = str.length(); 
    if (n == 0) { 
     System.out.println(prefix); 
    } else { 
     premutationFor(0, n, prefix, str); 
    } 
}