Java Rekursiv 2 Strings vergleichen

[hacklschorsch]

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.

 

[DerZong]

Da ich davon ausgehe, dass nicht die Funktion String.equal(String) verwendet werden soll, musst du mehrere Dinge prüfen:

• Zu erst überprüfen, ob die Länge der Strings gleich ist ( String.length() ) - wenn ungleich, dann muss er ja sowieso nicht weiter machen
• Dann nacheinander jedes einzelne Zeichen der Reihe nach vergleichen ( String.charAt(Stelle) ) - im Prinzip egal, wo du dabei anfängst - nur zweckmäßig nicht irgend wo in der Mitte
• Sind diese gleich, so die Methode wieder aufrufen - diesmal aber den String abzüglich der schon geprüften Stelle ( String.substring(Beginn, Ende) )
• Jeweilige Abbruchbedingungen sollten sein, dass keine Stelle des Ursprungsstrings mehr über ist, die verglichenen Stellen unterschiedlich sind, oder aber, dass die Strings eine unterschiedliche Länge haben.

 

[hacklschorsch]

hab so was im Kopf

boolean recfunction(String s1, String s2){
// hier prüfen ob länge gleich ist

  if(s1.charAt(1)==s2.charAt(1)){
         recfunction(s1.substring(1), s2.substring(1))
         return true
   }

Teste später mal

 

[hacklschorsch]

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);
		
		
	}
}

Bis auf das, das mir immer eine StringIndexOutOfBoundsException ( if(s1.length()!=0 || s2.length() != 0) )wirft. So sollte es doch aussehen oder???

 

[DerZong]

Denke mal, die IndexOutOfBoundsException bekommst du, da die Rekursion auch dann noch ausgeführt werden soll, wenn im String eigentlich keine Zeichen mehr drin sein können. Solltest also noch vor dem rekursiven Aufruf prüfen, ob der String noch mindestens 1 Zeichen lang ist

 

[hacklschorsch]

Alles klar. aber die rekursion stimmt so, oder?

 

[DerZong]

Denke, dass es so funktionieren sollte, habs selber auch nochmal nachgebaut, und läuft (nagel mich aber nicht drauf fest, wenn der Code nicht optimal ist/abläuft )

public class Rekursion { 
static int x = 0; 
    static boolean recCompare(String s1, String s2) { 
         
        //System.out.println(s1+s2); 
        x++; 
         
        if(s1.length() != s2.length()) 
            return false; 
        if(s1.length()==0 && s2.length()==0)
        	return true;
         
        while (s1.length()>0 && s2.length()>0 && s1.charAt(0)==s2.charAt(0)){ 
             
            if(s1.length()!=0 || s2.length() != 0) 
                //System.out.println(s1+s2);         
            if (s1.length() != 0 && s2.length() != 0)
            	return recCompare(s1.substring(1), s2.substring(1));
        } 
                 
        return false; 
         
    } 
     
    public static void main (String[] args) { 
     
        String s1 = "Hallohallöle"; 
        String s2 = "Hallohallöle"; 
        boolean vergleich = recCompare(s1,s2) ; 
        System.out.println("Vergleich zweier Strings");
        System.out.println("String 1:\t" + s1);
        System.out.println("String 2:\t" + s2);
        System.out.println("Ausgang des Vergleichs: "+vergleich);
        System.out.println("Durchläufe: " + x);
    } 
}

 

[hacklschorsch]

Perfekt. Haut alles hin. Vielen Dank

 

[hacklschorsch]

In einer der Letzten Klausuren war mal eine Rekursion daran die so ausgesehen hat. ( soweit ich mich erinnern kann )

rek(Rational a, Rational b)

Man sollte vergleichen ob beide gleich sind. Mehr stand da nicht.

Weis jemand noch andere gute Rekursionsaugaben.
Fibunacci, Hanoi, Sum sind kein Problem!

 

[DerZong]

Einige Sortieralgorithmen sind auch rekursiv - z. B. QuickSort oder MergeSort