Rekursiv 2 Strings vergleichen

[duuugle]

Hab schon einiges an Java Erfahrung. Hab da eine alte Klausur von der FH und würde gerne wissen, wie ich 2 Strings rekusriv vergleiche. Hier mal die Anageb:

geg: 2 STrings s1 und s2 beliebiger Länge. Rekursive Funktion soll true zurückgeben, wenn beide gleich sind.

so soll es aussehen.

static boolean recfunktion(String s1, String s2) {

}

Hab schon per google gesucht, aber finde nichts. Alles was ich finde, ist rekusriv iregnwas mit int-werten machen. Das kann ich, aber nicht mit Strings.

Hoffe jemand weis da was.

 

[FelixB]

der Unterschied ist doch gar nicht so groß.

betrachte einen String als Folge von Zeichen. Du vergleichst die ersten beiden und erhältst ein boolean. Anschließend machst du solange mit den nächsten Zeichen weiter, bis entweder ein String zuende ist oder ein false kommt.

Tipp:

return (c1 == c2) && recfunction(substring1, substring2)

 

[moormaster]

Macht sich sicher gut für Strings, deren Länge die Stackgröße überschreiten... ^^

 

[FelixB]

ist doch nur ne Klausuraufgabe...

 

[Guest]

Stimmt das so, denn es soll unbedingt als Rekursion gelöst werden, denn sonst sind es 0 Punkte???

public class Rekursion {
static int x=0;
	static boolean recCompare(String s1, String s2) {
		
		System.out.println(s1+s2);
		System.out.println(x++);
		
		while(  s1.length()!=0 && s2.length()!=0){
			
			recCompare(s1.substring(0,s1.length()-1),s2.substring(0,s2.length()-1))  ;
			System.out.println("fertig");
			return true;
		
		}
		return false;
			
		
	}
	

	
	
	
	public static void main (String... args) {
	
		String s1 = "Hallo";
		String s2 = "Hallo";
		
		System.out.println( recCompare(s1,s2) );
		
		char last  = s1.charAt( s1.length() - 1) ;
		
		System.out.println(last);
		
		
		
		
		
	}
}

 

[Guest]

Stimmt das so, denn es soll unbedingt als Rekursion gelöst werden, denn sonst sind es 0 Punkte???

public class Rekursion {
//static int x=0;
	static boolean recCompare(String s1, String s2) {
		
		System.out.println(s1+s2);
	//	System.out.println(x++);
		
		while(  s1.length()!=0 && s2.length()!=0){
			
			recCompare(s1.substring(0,s1.length()-1),s2.substring(0,s2.length()-1))  ;
			System.out.println("fertig");
			return true;
		
		}
		return false;
			
		
	}
	

	
	
	
	public static void main (String... args) {
	
		String s1 = "Hallo";
		String s2 = "Hallo";
		
		System.out.println( recCompare(s1,s2) );
		
		char last  = s1.charAt( s1.length() - 1) ;
		
		System.out.println(last);
		
		
		
		
		
	}
}

 

[duuugle]

Sorry hab wohl nach dem einloggen das ganze wieder geschrieben.

 

[FelixB]

wo vergleichst du die Zeichen? momentan wird nur die Länge verglichen...

 

[moormaster]

Stimmt das so, denn es soll unbedingt als Rekursion gelöst werden, denn sonst sind es 0 Punkte???

Das kannst du doch leicht testen, indem du es mit einigen Strings ausprobierst?

Den Sinn der while-Schleife versteh ich allerdings nicht.

Solange s1 und s2 leer sind rufe sich selbst auf, gebe "fertig" aus und verlasse (!!) die Schleife indem true zurückgegeben wird.

Ein einfaches if genügt anstelle der Schleife.

So nun zum Inhaltlichen:

Deine Rückgabewerte sind doch völlig willkürlich und sagen überhaupt nichts darüber aus, ob der String gleich ist oder nicht.

Du rufst z.B. deine Methode rekursiv auf ohne das Ergebnis weiterzuverarbeiten. Statt dessen wird dann einfach true zurückgegeben. Was ist, wenn der Rekursive Aufruf false zurückgibt? In dem Fall würdest du immer ein true daraus machen.

Ein rekursiver Vergleich 2er Strings müsste eher so ablaufen:

 Methode recCompare(String s1, String s2)
 {
   wenn s1 und s2 unterschiedlich lang sind, gebe false zurück (Strings sind unterschiedlich)

   sind s1 und s2 jeweils von der Länge 0, gebe true zurück (leere Strings sind immer identisch)

   wenn der erste Buchstabe von s1 sich vom ersten Buchstaben aus s2 unterscheidet, gebe false zurück (Strings sind unterschiedlich)

   rufe recCompare(s1.substring(1), s2.substring(1)) auf und gebe dessen Ergebnis zurück
   (erste Buchstaben von s1 sowie von s2 werden weglassen durch substring(1))
 }

 

[duuugle]

Du hast recht. Werd mir das ganze noch mal genau anschauen.
Danke

 

[duuugle]

public class Rekursion {
static int x = 0;
    static boolean recCompare(String s1, String s2) {
        
        //System.out.println(s1+s2);
        System.out.println(x++);
        
        if(s1.length() != s2.length())
            return false;
        
        
        while (s1.charAt(0)==s2.charAt(0)){
            
            if(s1.length()!=0 || s2.length() != 0)
                System.out.println(s1+s2);        
        
             return recCompare(s1.substring(1), s2.substring(1));
        }
                
        return false;
        
    }
    
    public static void main (String... args) throws IOException {
    
        String s1 = "Hallo";
        String s2 = "Hallo";
        
        System.out.println( recCompare(s1,s2) );
        
        char last  = s1.charAt( s1.length() - 1) ;
        
        System.out.println(last);
        
        
    }
}

kann mir jemand sagen warum mir eine StringIndexOutOfBoundsException wirft

 

[moormaster]

Weil in deiner Rekursion keine Abbruchbedingung drin steckt.

Das einzige Mal, wann ein endgültiges Ergebnis zurückgegeben wird, ist wenn sich die Länge der Eingabestrings unterscheiden. Sind sie gleich, dann rufst du immer wieder die Funktion rekursiv auf und entfernst das erste Zeichen. Undzwar auch dann, wenn es gar kein erstes Zeichen mehr gibt und genau das wird die Stelle sein, welche diesen Fehler verursacht.

Wie ich schon vorher angedeutet hab, musst du, wenn beide Strings leer sind, sofort ein true zurückgeben, weil sie dann identisch sind. Dann wird auch kein weiterer rekursiver Aufruf mehr stattfinden, welcher aus den leeren Strings das erste Zeichen versucht wegzulassen

Des weiteren hast du die while Schleife immernoch nicht gegen eine if Bedingung ausgetauscht... welchen Sinn macht eine Schleife, die eh nur höchstens einmal durchlaufen werden kann, weil ein return Befehl drin steht?

 

[duuugle]

Alles klar, jetzt hab ich den Fehler auch entdeckt. Danke

Ja es wäre besser wenn ich statt der while eine if schleife mache.

 

[VuuRWerK]

[...] eine if schleife [...]

Sorry aber für diese Ausage wäre ich dafür Dich zu kicken/bannen/löschen/Atomrakete/... Nein, im Ernst, BITTE NIE eine if-Schleife sondern ein Statement oder wie auch immer Du es nennen willst, aber eine if-Schleife gibt es nicht!!!!!!!!!

Danke.

Gut Schuß
VuuRWerK

 

[moormaster]

Solange while-Schleifen mit max. einem Durchlauf erlaubt sind, sind auch if-Schleifen mit höchstens einem Durchlauf erlaubt...