Fehlersuche bei rekursiver Methode

B

babuschka

Top Contributor
Die folgende Methode reverse bekommt als Parameter einen String, der mittels der Methode reverseHelper rekursiv rückwärts in einen StringBuilder geschrieben werden soll.

Doch leider hat der Programmierer einen Fehler gemacht. Der String wird nicht umgedreht, sondern wieder genauso zurückgegeben.

Hier der Code:

Java: 
public static String reverse(String s) {
   StringBuilder b = new StringBuilder();
   reverseHelper(b, s, s.length()-1);
   return b.toString();
}

private static void reverseHelper(StringBuilder b, String s, int index) {
   if( index == -1) {
     return;
} else {
      reverseHelper(b,s,index-1);
      b.append(s.charAt(index));
      return;

}
}


So, also ich nehme mal den String "Hund".

Jetzt rufe ich reverse("Hund"); auf.

Es wird ein neuer leerer StringBuilder erzeugt.

Die Methode reverseHelper(b, "Hund", 3); wird aufgerufen.


Da 3 ungleich -1 ist, wird der else-Zweig angesprungen und

reverseHelper(b,"Hund", 2) aufgerufen, dann fängt es doch wieder neu an, also
reverseHelper(b,"Hund",1) und wieder neu also
reverseHelper(b,"Hund", 0) und schließlich
reverseHelper(b,"Hund",-1) und damit return und Ende.

Und DANN kommt man doch erst in die Zeile 12?

Also wird an den StringBuilder was angehängt? Ein D?

Und wieso kommt wieder "Hund" heraus, kann mir das jemand erklären, ich scheine den Ablauf nicht richtig zu verstehen.
 
Zuletzt bearbeitet von einem Moderator:
E

eRaaaa

Top Contributor
Zeile 11 und 12 mal tauschen und dann nochmal überlegen :) (welche Aufrufe in welcher Reihenfolge erfolgen und vor allem WANN!)
 
B

babuschka

Top Contributor
Es geht aber darum, daß man in der Aufgabe erstmal verstehen soll, wieso wieder der gleiche Code ausgegeben wird.

Ich verstehe nicht, wieso bei dem Code, wie er so vorgegeben ist, wieder "Hund" rauskommt.


(Über die Fehlerbeseitigung soll man sich dann erst Gedanken machen.)
 
E

eRaaaa

Top Contributor
Deshalb sollst du dir mal Gedanken machen wie der "Stack" aussieht.

reverseHelper(b, s, index - 1);
b.append(s.charAt(index));

Das ist die entscheidende Stelle!
Es wird also erstmal immer wieder die reverse Methoden aufgerufen BEVOR etwas angehängt wird, d.h. Index von 3 bis 0(bzw -1), d.h. der Aufruf mit dem Index = 0 ist sozusagen der Letzte, dann wird aber die Methoden ja weiter ausgeführt(da wo sie durch den rekursiven Aufruf unterbrochen wurde), d.h. es kommt dann die Zeile mit dem b.append an die Reihe (aber mit dem Index 0 zuerst!)
Wie gesagt, zeichne es dir mal auf oder so, oder spiele es Stück für Stück selbst durch!
 
L

lukas93

Mitglied
okay... ich geb mal mein bestes... also erstmal sind deine aussagen über den ablauf alle richtig!
also überlegen wir mal, was
Java: 
b.append(s.charAt(index));
bewirkt.
es wird dem String bilder ein zeichen zugefügt... und zwar das zeichen, das über
Java: 
s.charAt(index)
definiert wird!
du befindest dich noch auf der letzten ebene also auf der mit index = 0 deswegen wird die erste Stelle des Strings zu dem stringBuilder hinzugefügt.
du musst nur anstatt dem parameter index etwas übergeben, was die letzte stelle bezeichnet
probier es mal mit
Java: 
b.append(s.charAt(s.length()-1-index))
 
S

SlaterB

Gast
reverseHelper(b,"Hund",-1) führt zu einem return ohne was zu tun, richtig,

nun musst du überblicken wie es weitergeht, die vorherigen Aufrufe sind nicht auch automatisch alle beendet,
sondern wurden für weitere Aufrufe unterbrochen, wo stehen sie, wie geht es dort weiter?
hast du dazu keine Vorstellung oder bisher nur gedacht dass es mit dem return komplett zu Ende ist?
 
B

babuschka

Top Contributor
Ich habe ja verstanden, dass man bei append also mit index gleich 0 beginnt.

Aber wo kommen denn die anderen Stellen her?

Woher bekommt man s.chatAt(1), s.charAt(2),...

??
 
S

SlaterB

Gast
es gibt doch lauter rekursive Aufrufe, neben -1 und 0 auch 1 und 2 usw.,
du selber schreibst es:
> reverseHelper(b,"Hund", 2) aufgerufen, dann fängt es doch wieder neu an, also
> reverseHelper(b,"Hund",1) und wieder neu also
> reverseHelper(b,"Hund", 0) und schließlich
> reverseHelper(b,"Hund",-1) und damit return und Ende.


alle fügen irgendwann etwas ein, mache dir nur dem Ablauf klar
 
B

babuschka

Top Contributor
SlaterB hat gesagt.:
hast du dazu keine Vorstellung oder bisher nur gedacht dass es mit dem return komplett zu Ende ist?
Zum Vergrößern anklicken....

Ich kann mir das nicht vorstellen.

Ich habe es mir wirklich so gedacht, daß die Aufrufe sozusagen verloren gehen und man am Ende eben nur die Stelle 0 anhängt.


Aber dem ist nicht so.


Aber irgendwie fehlt mir noch das Verständnis.
 
S

SlaterB

Gast
reverseHelper(b, "Hund", 3); ruft reverseHelper(b, "Hund", 2); auf, richtig,
wenn das fertig ist geht es aber mit der nächsten Zeile weiter, Zeile 12, ein 'd' wird eingefügt,

was passiert dazwischen?
reverseHelper(b, "Hund", 2); ruft reverseHelper(b, "Hund", 1); auf, richtig,
wenn das fertig ist geht es aber mit der nächsten Zeile weiter, ein 'n' wird eingefügt,
das passiert offensichtlich BEVOR reverseHelper(b, "Hund", 2); fertig ist und das 'd' vom 3er-Aufruf kommt,
also erst 'n', dann 'd'

so kann man sich ja weiterdenken dass 'H' und 'u' von den inneren Aufrufen auch noch vorher drankommen
 
B

babuschka

Top Contributor
Vielen Dank, jetzt habe ich das verstanden!


Das sollen wir nun mit möglichst wenig Änderungen so umändern, daß die Methode den erwünschten Effekt hat.


Ich hab mir das aufgemalt.

Es ist meines Erachtens ausreichend, wenn man die Zeilen 11 und 12 tauscht.

Istdas so? Oder muss mehr verändert werden?
 
F

Firephoenix

Gast
Aber irgendwie fehlt mir noch das Verständnis.
Zum Vergrößern anklicken....

Wenn die Zeitangabe aus einem älterem Thread stimmt beschäftigst du dich mittlerweile seit über 3 Monaten mit Java auf Uniniveau - jetzt nur aus den Threads zu entnehmen woran es hängt, ob es Verständnisprobleme etc sind, ist so gut wie nicht zu beurteilen, auch kenne ich euren Stoff und die Qualität der Vorlesung nicht - aber fundierte Grundkenntnisse sehen wirklich anders aus ;)

Genauso wie ich nicht verstehe, was so schlimm daran ist, sich einfach mal ein Blatt Papier zu greifen und sich den Kram aufzumalen. Dafür muss man nur wissen, dass Methoden aufgerufen werden, und wie die Aufrufverschachtelung funktioniert -> du kannst quasi direkt den Code der Methode einsetzen (zum Verständnis, intern wird sich nur die Stelle gemerkt und ab da das zwischenergebnis der Methode berechnet, für genaueres solltest du dich mal über den Stack von Java informieren, falls euer dozent dazu noch keine Worte verloren hat).

Der Code, reverse wird mit "Hund" aufgerufen:
Java: 
public static String reverse( String s )
    {
        StringBuilder b = new StringBuilder();
        reverseHelper( b, s, s.length() - 1 );
        return b.toString();
    }

->

"Hund" wird über s an reverseHelper übergeben, length = 4, length -1 entsprechend = 3
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    reverseHelper( b, "Hund", 3 );
    return b.toString();
}

Bevor du mit dem return weitermachst muss der aufruf von reverseHelper ausgeführt werden:

3 ist nicht -1, also gehst du in den else-Zweig und führst wieder reverse Helper aus
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            reverseHelper( b, "Hund", 2 );
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}



Wieder mit eingefügtem Code:
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            private static void reverseHelper( StringBuilder b, String "Hund", int 2 )
            {
                if ( 2 == -1 )
                {
                    return;
                }
                else
                {
                    reverseHelper( b, "Hund", 1 );
                    b.append( s.charAt( 2 ) );
                    return;

                }
            }
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}

Wie du siehst betrittst du wieder den Else-Zweig, du rufst also reverseHelper mit 1 auf:
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            private static void reverseHelper( StringBuilder b, String "Hund", int 2 )
            {
                if ( 2 == -1 )
                {
                    return;
                }
                else
                {
                    private static void reverseHelper( StringBuilder b, String "Hund", int 1 )
                    {
                        if ( 1 == -1 )
                        {
                            return;
                        }
                        else
                        {
                            reverseHelper( b, "Hund", 0 );
                            b.append( s.charAt( 1 ) );
                            return;

                        }
                    }
                    b.append( s.charAt( 2 ) );
                    return;

                }
            }
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}

1 ist immer noch nicht -1, du rufst reverse-helper also mit 0 auf:
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            private static void reverseHelper( StringBuilder b, String "Hund", int 2 )
            {
                if ( 2 == -1 )
                {
                    return;
                }
                else
                {
                    private static void reverseHelper( StringBuilder b, String "Hund", int 1 )
                    {
                        if ( 1 == -1 )
                        {
                            return;
                        }
                        else
                        {
                            private static void reverseHelper( StringBuilder b, String "Hund", int 0 )
                            {
                                if ( 0 == -1 )
                                {
                                    return;
                                }
                                else
                                {
                                    reverseHelper( b, "Hund", -1 );
                                    b.append( s.charAt( 0 ) );
                                    return;

                                }
                            }
                            b.append( s.charAt( 1 ) );
                            return;

                        }
                    }
                    b.append( s.charAt( 2 ) );
                    return;

                }
            }
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}

0 ist auch nicht -1, du rufst reverse-Helper mit -1 auf:
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            private static void reverseHelper( StringBuilder b, String "Hund", int 2 )
            {
                if ( 2 == -1 )
                {
                    return;
                }
                else
                {
                    private static void reverseHelper( StringBuilder b, String "Hund", int 1 )
                    {
                        if ( 1 == -1 )
                        {
                            return;
                        }
                        else
                        {
                            private static void reverseHelper( StringBuilder b, String "Hund", int 0 )
                            {
                                if ( 0 == -1 )
                                {
                                    return;
                                }
                                else
                                {
                                    private static void reverseHelper( StringBuilder b, String "Hund", int -1 )
                                    {
                                        if ( -1 == -1 )
                                        {
                                            return;
                                        }
                                        else
                                        {
                                            reverseHelper( b, "Hund", -2 );
                                            b.append( s.charAt( -1 ) );
                                            return;

                                        }
                                    }
                                    b.append( s.charAt( 0 ) );
                                    return;

                                }
                            }
                            b.append( s.charAt( 1 ) );
                            return;

                        }
                    }
                    b.append( s.charAt( 2 ) );
                    return;

                }
            }
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}

Der innere Aufruf mit -1 bricht jetzt die rekursion ab und gibt nichts zurück (siehe kommentar)
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            private static void reverseHelper( StringBuilder b, String "Hund", int 2 )
            {
                if ( 2 == -1 )
                {
                    return;
                }
                else
                {
                    private static void reverseHelper( StringBuilder b, String "Hund", int 1 )
                    {
                        if ( 1 == -1 )
                        {
                            return;
                        }
                        else
                        {
                            private static void reverseHelper( StringBuilder b, String "Hund", int 0 )
                            {
                                if ( 0 == -1 )
                                {
                                    return;
                                }
                                else
                                {
                                    //Hier wird returned - als nächstes kommt b-append.
                                    b.append( s.charAt( 0 ) );
                                    return;

                                }
                            }
                            b.append( s.charAt( 1 ) );
                            return;

                        }
                    }
                    b.append( s.charAt( 2 ) );
                    return;

                }
            }
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}

an den StringBuilder wird jetzt der Char an der Stelle 0 gehängt, das "H"
, dannach bricht auch dieser Methodenaufruf ab
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            private static void reverseHelper( StringBuilder b, String "Hund", int 2 )
            {
                if ( 2 == -1 )
                {
                    return;
                }
                else
                {
                    private static void reverseHelper( StringBuilder b, String "Hund", int 1 )
                    {
                        if ( 1 == -1 )
                        {
                            return;
                        }
                        else
                        {
                            //Hier wurde returned
                            b.append( s.charAt( 1 ) );
                            return;

                        }
                    }
                    b.append( s.charAt( 2 ) );
                    return;

                }
            }
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}

Wie man sieht wird jetzt der 1. Char angehängt,
also ist der inhalt von b jetzt "H"+"u", dannach returned auch diese Methodeninstanz

Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
            private static void reverseHelper( StringBuilder b, String "Hund", int 2 )
            {
                if ( 2 == -1 )
                {
                    return;
                }
                else
                {
                  //Hier wurde returned
                    b.append( s.charAt( 2 ) );
                    return;

                }
            }
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}

Jetzt hängst du den Char von Position 2 (das "n") an:
b ist jetzt "H"+"u"+"n"
weiter geht es so:
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
    private static void reverseHelper( StringBuilder b, String "Hund", int 3 )
    {
        if ( 3 == -1 )
        {
            return;
        }
        else
        {
          //Hier wurde returned
            b.append( s.charAt( 3 ) );
            return;

        }
    }
    return b.toString();
}
Jetzt hängst du den char von Position 3 an, das "d"
b = "H"+"u"+"n"+"d"
, dannach bricht auch dieser aufruf ab:
Java: 
public static String reverse( "Hund" )
{
    StringBuilder b = new StringBuilder();
  //Hier wurde returned
    return b.toString();
}

der letzte Befehl ist return b.toString() = "Hund"

(Sry für diejenigen denen das zu lang war, aber ich denke so ist es anschaulich ;) )

Gruß
 
B

babuschka

Top Contributor
Danke, Firephoenix für die Ausführlichkeit.

Deine Kritik ist berechtigt, aber die ersten Schritte hatte ich immerhin, also ganz bei Null hättest Du nicht anfangen müssen.


Das Thema "Rekursion" haben wir gerade begonnen und ich finde, daran muss man sich erstmal gewöhnen, dennoch möchte ich natürlich nicht bestreiten, dass ich ein Talent dazu habe, mich dumm anzustellen.




----

Okay, dann tausche ich die Zeilen 11 und 12 und alles ist gut.
Hab das auch nochmal in der gleichen Ausführlichkeit (wie eben Firephoenix) aufgeschrieben und ja: Es wird dann "dnuH" zurückgegeben. :toll:
 
Zuletzt bearbeitet von einem Moderator:

Aktuelle Jobs

Neue Themen


Oben