Wie löse ich diese Java-Rekursion ohne einen anderen Fall?

Question

Wenn ich schreibe: DoSomething (3), druckt das Terminal 1213121, aber ich bin nicht in der Lage, den rekursiven Prozess zu folgen, da es nur einen Basisfall und keinen anderen Fall gibt. Was macht die Funktion, wenn n == 0? Und wie geht das den rekursiven Schritt?

Answer 1

Rekursion ist nicht notwendig, base Fall zu haben. Es erfordert nur 2 Dinge:

1. ein Punkt das Programm beendet werden kann (i == 0 in diesem Fall)
2. jedem rekursiven Aufruf läuft in einer Richtung, dass Punkt (doSomething(n - 1) in diesem Fall statt doSomething(n + 1)) nähert

Wenn Sie in einem base Fall denken bevorzugen, ist der Code genau das gleiche wie:

public void doSomething(int n){ 
    if (n <= 0) { 
     return; 
    } 

    doSomething(n-1); 
    System.out.print(n); 
    doSomething(n-1); 
} 

Falls Sie interessiert sind, ähnelt Ihre Codelogik der rekursiven Version von inorder traversal des Binärbaums. Sie können sich für weitere Einsichten auf https://en.wikipedia.org/wiki/Tree_traversal#In-order beziehen.

Answer 2

Was macht die Funktion, wenn n == 0?

Absolut nichts.

Und wie geht das den rekursiven Schritt?

Es wird nicht fortgefahren.

Und es sollte nicht fortfahren. Wenn n <= 0 sollte der Code nicht weiter recurse.

Jemand riet Ihnen, den Code mit einem Debugger zu starten, um Ihnen zu visualisieren was vor sich geht. Das sollte man mit diesem konzeptionellen Problem helfen zu:

Ich bin nicht in der Lage dem rekursiven Prozess zu folgen, weil es nur ein Basisfall ist und kein else Fall.

Sie haben die Grundlagen der Rekursion falsch verstanden. Es erfordert keinen else Fall. Was ist eigentlich erfordert, ist eine Möglichkeit, die Rekursion zu stoppen. Ein else Fall ist eine Möglichkeit, aber es gibt eine Vielzahl von anderen.

Oder ..., um es zu Ihrem Beispiel zu bringen ... Ihr Code auf diese entspricht:

public void doSomething(int n){ 
    if (n > 0){ 
      doSomething(n-1); 
      System.out.print(n); 
      doSomething(n-1); 
    } else { 
      // this is a comment 
    } 
} 

Jetzt gibt es einen else Fall ... was ein leerer Block ist. Oder Sie könnten eine redundante return Anweisung in den Block schreiben. (Ich nehme an, dass Sie herausfinden können warum es redundant ist!)

Answer 3

Ich denke, dass dieser Code ein gutes Beispiel für Rekursion ist. Es erzeugt alle Kombinationen mit 0 und 1 und Länge 5 rekursiv, ein Muster Ergebnisse:

Ergebnis:

00000 
00001 
00010 
00011 
00100 
00101 
00110 
00111 
01000 
01001 
01010 
01011 
01100 
01101 
01110 
01111 
10000 
10001 
10010 
10011 
10100 
10101 
10110 
10111 
11000 
11001 
11010 
11011 
11100 
11101 
11110 
11111 

Code:

class Stringhelper { 
    public Stringhelper() { 
    } 
    public String getstring(String string,int beginning,int ending) { 
     if (string.length() != 0) { 
     String newstring=""; 
     for (int iter=Math.abs(beginning); iter < ending && iter < string.length(); iter=iter+1) { 
       newstring=newstring+Character.toString(string.charAt(iter)); 
     } 
     return newstring; 
     } 
     else { 
     return ""; 
     } 
    } 
} 



public class Counter { 
    public String abil=""; //Possible Combinations 
    public int iter=0; 
    public Stringhelper shelper=new Stringhelper(); 
    public void loop(int iter) { 
     for (int i=0; i < 2; i++) { 
       abil=shelper.getstring(abil,0,iter); //Crop everything until this char, if string was 010, for and iter is 2 : 01+result of this loop 
       abil=abil+Integer.toString(i); 
       if (iter==4) { //0,1,2,3,4=Length 5 
        System.out.println(abil); 
       } 
       else { 
        loop(iter+1); 
       } 
     } 
    } 
    public Counter() { 
     loop(iter); 
    } 
    public static void main(String args[]){ 
     new Counter(); 
    } 
} 

Es funktioniert so:

Für Beispiel mit der Länge 2 * 2 = 4 Kombinationen.

ist:

00 
01 
10 
11 

Aber wie es das macht produzieren?

Es funktioniert so:

Ersten Aufruf: loop (0) ausgeführt wird.

Die Schleife hat eigentlich i=0. Es schreibt es nieder. Die Zeichenfolge lautet "0". Jetzt startet es loop(1). Diese Funktion hat i=0 zuerst, fügt es hinzu, jetzt ist die Zeichenkette "00", es bemerkt, dass es bereits die zweite Schleife ist, und so druckt es es, aber startet die Funktion nicht erneut. "00" wird ausgedruckt. Jetzt geht die Schleife weiter. i=1. Zuerst versucht es, alle Zeichen bis jetzt zu schneiden, also von "00" bleibt dort nur die erste Null, also sein "0". Jetzt ist "1" angehängt, String ist "01". Es merkt, dass es bereits die zweite Schleife ist, und so druckt es es, aber startet die Funktion nicht erneut. "01" wird gedruckt. Diese Funktion wurde fortgesetzt und es geht zurück zur ersten Funktion. Die Schleife läuft jetzt weiter, sie versucht alle Zeichen bis jetzt zu schneiden, also haben wir jetzt eine gelöschte Zeichenkette "". Es startet loop(1). Diese Funktion hat i=0 zuerst, fügt es der Zeichenfolge hinzu, jetzt ist die Zeichenfolge "10", es merkt, dass es bereits die zweite Schleife ist, und so druckt es, aber startet die Funktion nicht erneut. "10" wird ausgedruckt. Jetzt geht die Schleife weiter. i=1. Zuerst versucht es, alle Zeichen bis jetzt zu schneiden, also von "10", dort bleibt nur das erste Zeichen, also sein "1". Jetzt ist "1" angehängt, String ist "11". Es merkt, dass es bereits die zweite Schleife ist, und so druckt es es, aber startet die Funktion nicht erneut. "11" wird gedruckt. Kein Prozess läuft mehr.