Rekursion, aber wie?

[kurwajebana]

Hallo! Ich komme nicht auf die rekursive Lösung dieser Aufgabe: Es sollen alle Leerzeichen gezählt werden! Die Iterative Lösung habe ich Auskommentiert:

public static int numberOfSpaces(String s) {
        if (s==null) return 0;
        return numberOfSpaces(s........
        
    }
// Iterative Lösung:        
//        int count=0;
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i)==' ') count++;
//        }
//        return count;
//    }
    public static void main(String[] args) {
        System.out.println(numberOfSpaces("Hallo Welt"));
    }
    
}

Kann mir einer helfen? Danke

 

[player1]

Hm. Man kann das Problem rekursiv lösen, aber is ist das in diesem Fall überhaupt sinnvoll?

Die Strategie, die man da jedenfalls folgt nennt sich Divide&Conquer (Teile und Herrsche). In deinem konkreten Fall heißt das: Teile den String in ein kleinstmögliches Problem und löse das Problem -> Teste ob ein einzelner Charakter ein Leerzeichen ist.

Eine Lösung ist:

    public  int numberOfSpaces(String s) 
    {
        System.out.println(s); // Testaudruck
        if ( s.length() == 0) {

            return 0;
        
        } else {
            
            if ( s.charAt(0) == ' ') { //wenn erster charakter des mitgegebenen Strings ==  " "
                return numberOfSpaces(s.substring(1)) +1; // gebe Resultat von Methode + dieses zurück
            } else {
                return numberOfSpaces(s.substring(1)); //gebe nur Resultat von Methode zurück
            }
        
        }
    }

 

[kurwajebana]

Aha, danke für die Antwort!
Ich versteh aber nicht wie man auf das Ergebnis kommt:

 numberOfSpaces(s.substring(1)) +1;

Ich weis nur das sich hier die Methode immer wieder selbst aufruft, aber was da genau geschieht versteh ich nicht, vor allem: wie kann man einer Methode + 1 dazu addieren?!
Kann mir vielleicht jemand ein Tipp geben wie man eine Methode rekursive schreiben kann?

 

[zerix]

Hallo,

Ich weis nur das sich hier die Methode immer wieder selbst aufruft, aber was da genau geschieht versteh ich nicht, vor allem: wie kann man einer Methode + 1 dazu addieren?!

Es wird nicht der Methode die 1 hinzu addiert. Da die Methode den Rückgabewert int hat, liefert die Methode eine int-Zahl zurück und diese Zahl wird die 1 hinzu addiert. Also grob gesagt steht der Methoden-Aufruf stellvertretend für eine Zahl, ähnlich einer Variable.

Kann mir vielleicht jemand ein Tipp geben wie man eine Methode rekursive schreiben kann?

Man kann nicht alles rekursiv lösen. Deine Aufgabe kann man aber rekursiv lösen. Ich weiß nicht ganz wie ich es erklären soll, aber ich versuch es mal. Bei dem Object das rekursiv bearbeitet werden soll, muss eine spezielle Eigenschaft besitzen.
Z. B. String: ein String für sich ist ein String. Aber ein Teil davon ist auch ein String und ein Teil davon ist auch ein String.
Oder eine Liste(ArrayList o. ä.). Ein Teil einer Liste ist auch wieder eine Liste, usw.
Ich hoffe, das ist so halbwegs verständlich was ich da zeigen wollte.
Als nächstes muss sich die Aufgabe für jeden Teil das zu bearbeitenden Objects wiederholen. In deinem Fall ist die arbeit, dass du an jeder Stelle schaust ob es ein Leerzeichen ist.
Wenn diese Sachen erfüllt sind, steht der Rekursion eigentlich nichts mehr im Wege.
Der Rest ist dann ganz einfach. Du musst für einen Teil mit dem irgendwas gemacht werden soll alle Fälle abbacken. In deinem Fall, schaust du die eine Stelle des Strings an, die erste oder die letzte. Die erste bietet sich an.
Dann schaust du.
1. Hab ich überhaupt einen String, der ein Zeichen besitzt. Falls nicht, gibts auch keine Leerzeichen.

if ( s.length() == 0) {
      return 0;
}

2. Ist an der ersten Stelle ein Leerzeichen, falls ja wird das eine Leerzeichen + die restlichen Leerzeichen zurück gegeben, sonst nur die restlichen Leerzeichen.

else {
            
            if ( s.charAt(0) == ' ') { //wenn erster charakter des mitgegebenen Strings ==  " "
                return numberOfSpaces(s.substring(1)) +1; // gebe Resultat von Methode + dieses zurück
            } else {
                return numberOfSpaces(s.substring(1)); //gebe nur Resultat von Methode zurück
            }
        
        }

So hast du alle Fälle abgefangen die auftreten können.
Sieh dich einfach mal als Abteilungsleiter. Du bekommst einen String und sollst Leerzeichen zählen. Du schaust dir dann einfach die erste Stelle an und schaust was das ist(Leerzeichen oder nicht). Dann gibst du die arbeit einfach an einen Untergebenen weiter(rekursiver Methodenaufruf) und der soll dir sagen wieviele Leerzeichen in dem restlichen String vorhanden sind. Der Rest erledigt sich dann von alleine.

Ich hoffe ich hab das ganze halbwegs verständlich erklärt. Falls ich was vergessen haben sollte, kann man das gerne ergänzen.

MFG

zEriX

 

[player1]

Z. B. String: ein String für sich ist ein String. Aber ein Teil davon ist auch ein String und ein Teil davon ist auch ein String.
Oder eine Liste(ArrayList o. ä.). Ein Teil einer Liste ist auch wieder eine Liste, usw.
Ich hoffe, das ist so halbwegs verständlich was ich da zeigen wollte.

Ein anderes sehr gutes Beispiel ist ein stinknormaler Baum: Sieh den Stamm ganz unten als Ast.
Dieser Ast, hat Äste, die wiederrum auch wieder Äste haben usw...

Wenn man ein Problem rekursiv lösen will, löst man zuerst einmal das kleinstmögliche Problem: Ein Stamm (Ast) der ein Ast hat. Den Satz könntest du jetzt rekursiv weiterführen:
Ein Ast hat Äste haben Äste haben Äste haben Äste......usw