Rekursion

[yeha]

Hallo,
ich habe Probleme mit der Funktionsweise von Rekusion.
hier ein Beispiel

 public static int BerechneQuersumme(int zahl)
{
if(zahl<10)
{
return zahl;
}
return BerechneQuersumme(zahl/10) +BerechneQuersumme(zahl%10);
}

mir ist ein Rätsel wieso das klappt, meinem Verständnis nach würde das ganze so ablaufen (mit der zahl 222) :
erster Durchlauf (222>10) also BerechneQuersumme(222/10) = 22 BerechneQuersumme(222%10)=2

zweiter Durchlauf(22>10) also BQ= 22/10= 12 22%10=2
dritter durchlauf(12>10) also 12/10=1 12%10=2
vierter durchlauf(1<10) deshalb gib 1 zurück.

und nun würde ich alle zwischschritte zusammen rechnen, also 22+2 + 12+ 2 + 1+ 2
und das würde nun mal ein falsches Resultat ergeben.
Ich wäre dankbar wenn mich jemand über meinen Denkfehler aufklären könnte

 

[Gucky]

Warum ist 22/10=12? Ich denkw, da liegt der Fehler.

 

[yeha]

haha, oh gott stimmt...

 

[yeha]

aber das ergebnis wäre trotzdem falsch. rauskommen soll ja 6.

 

[Tarrew]

Ich komme mit deiner Schreibweise nicht so ganz klar.
Aber du kannst dir ja mal so eine Art Aufrufbaum aufzeichnen, dann sollte dir klar werden, warum da 6 rauskommt.

 

[yeha]

Danke aber ich verstehe trotzdem nicht warum denn nachher nur Ergebnisse aus (zahl%10) und (wenn zahl <10) zusammen gerechnet wird.
das return beinhaltet ja auch (zahl/10), müsste doch dann heißen das 22 auch noch dazu gerechnet wird oder?
ich hoffe man versteht wo mein Problem liegt...

 

[franky27]

Nein 22 ist ja kein "Ergebnis" sondern nur der Parameter der beim nächsten Aufruf der Methode übergeben wird.

 

[yeha]

Achso, ich glaube ich habe es nun verstanden. Zahlen werden nur dazu addiert sofern sie kleiner als 10 sind, das heißt die Reste aus zahl%10 werden addiert da sie ja kleiner als 10 sind... mit 22 wird weiter durch 10 gerechnet da die Zahl ja noch größer als 10 ist, erst wenn die zahl soweit gekürzt wurde dass sie kleiner als 10 ist wird es dazu gerechnet

 

[franky27]

Ich würde mich an deiner Stelle mal ein wenig mit dem Debugger vertraut machen. Auf die Weise kannst du das Schritt für Schrtt durchgehen. Du machst dir einen Breakpoint in der Methode und kannst dann im Debugger Fenster alle variablen beobachten die du willst. Ausserdem siehst du im Debug Fenster wie die Methoden abgarbeitet werden (Stichwort Stack). So kannst du, abgesehen vom Verständnis des Aublaufes, auch einfach sehen ob du manuell Rechenfehler gemacht hast.

 

[yeha]

Danke für den Tipp

 

[nvidia]

Danke für den Tipp

Der Versuch das Problem mit einer baumartigen Rekursion zu lösen ist merkwürdig, da die gegebene Lösung in jedem weiteren Schritt sowieso nur ein Element abspaltet.

Zuerst sollte man das Problem in seiner Gesamtheit begreifen. Die Definition der Quersumme ist die Summe der Komponenten einer Zahl. Spielen wir also damit. Sei z = 123, unter Verwendung der Defintition folgt q = 1+2+3. Das kann noch nicht alles sein, also sind wir weiter neugierig. Es folgen q = (3+(2+(1))) und q = (1+(2+(3))), höchstinteressant! Wäre q eine Funktion könnte das auch so aussehen qs = q(3+(q(2+(q(1)))

Wir haben zwei neue, spannende Fakten erkannt. Erstens die Quersumme kann auch definiert werden aus der Summe einer Komponente von z mit der Quersumme über die restlichen Komponenten. Und Zweitens die Quersumme einer Komponente ist die Komponente selbst.

Mit diesem Wissen schreiten wir zur Lösung und bemerken das noch etwas fehlt. Wie zerlegen wir eine Zahl in eine Komponente und eine Zahl die die übrigen Komponenten enthält? Da wir gut in Mathe sind wissen wir das man durch % und / (Ganzzahldivision) an das Endelement und den davor enthaltenen Rest herankommt. D.h. wenn z=123 dann ist e = 123 % 10 = 3 und r = 123 / 10 = 12.

Bewaffnet mit den Erkenntnissen zu %,/, dass die Quersumme durch die Quersumme selbst definiert werden kann und die Quersumme einer einstelligen Zahl die Zahl selbst ist schreiben wir unsere Funktion.

    public static int quersumme(int zahl){
        //zahl ist einstellig
        if(zahl<10){
            return zahl;
        }
        //"Neue" Definition der Quersumme
        //Summe aus einer Komponente und der Quersumme über die restlichen Komponenten
        return (zahl % 10)  + quersumme(zahl / 10);
    }

Für diese Lösung braucht man weder das Wissen um einen Debugger oder die Funktionsweise des Stacks in Java. Sondern nur das Gerät zwischen den Schultern und ein wenig Zeit das Problem ordentlich zu durchdringen.

 

[franky27]

Für diese Lösung braucht man weder das Wissen um einen Debugger oder die Funktionsweise des Stacks in Java. Sondern nur das Gerät zwischen den Schultern und ein wenig Zeit das Problem ordentlich zu durchdringen.

Ich beziehe mich mal auf dieses Zitat, was ja auf meinen "Tipp" abzielt.
Ist ja alles schön und richtig was du sagst und auch ganz toll geschrieben. Ich sage auch nirgendwo das man dieses Wissen "braucht". Wenn der Thread Ersteller jedoch die Abarbeitung der Methode an sich nicht "durchdrungen" hat, bzw. bereits auf seinem Blatt einen Rechenfehler den er nicht erkannte, dann bringt ihm auch die schönsteMathe Nachilfe nicht viel um in Zukunft solche Methoden zu schreiben.

 

[nvidia]

[..] Wenn der Thread Ersteller jedoch die Abarbeitung der Methode an sich nicht "durchdrungen" hat[...]

Der Ersteller hat das Problem nicht durchdrungen, die stumpfe Fixierung auf die Abarbeitungsreihenfolge von Methoden führt bei Rekursion oft zu "Denkblockaden". Und bei diesem Problem folgt die Abarbeitungsreihenfolge aus dem Verständnis des Problems da es sich 1:1 so hinschreiben lässt.

Ich persönlich finde Versuche jmden Rekursion anhand von Methodenfolgen zu erläutern eher hinderlich da wäre ihm tatsächlich mehr mit Mathenachhilfe geholfen, weil es um ein abstrakteres Konzept geht welches unabhänig von Programmiersprachen ist.

 

[franky27]

Von einer stumpfen Fixierung redest aber auch nur du, davon habe ich nie gesprochen. Meine Antwort war klar auf seine Frage bezüglich der return Anweisungen bezogen. Im übrigen habe ICH auch nicht die Baumstruktur gezeichnet auf die du dich im ersten Satz beziehst.
Wir können ja OP einfach selbst entscheiden lassen, ob er mit deiner Antwort den Code hätte schreiben können. Wenn ja ist doch alles in Butter. Ich hätte es als Anfänger nicht gekonnt.

 

[nvidia]

Mit der stumpfen Fixierung bezog ich mich, wie aus dem Kontext ersichtlich, auf den ursprünglichen Post samt dem daraus resultierenden Ergebnis.

 

[franky27]

Inwieweit es jetzt hinderlich ist sich den Ablauf im Debugger anzuschauen, um die ursprüngliche Frage zur Rekursion zu verstehen, lassen wir dann einfach mal dahingestellt. Mehrere Wege führen ja bekanntlich zum Ziel und OP wird sich schon richtig entscheiden.

 

[yeha]

oha, ich sag jetzt mal nichts zu eurer Diskussion...
Also als ich grade nochmal über die Methode nachgedacht habe, bin ich zu dem Schluss gekommen ,dass ich doch nichts verstanden habe
Kann mir jemand nochmal in aller Deutlichkeit sagen, wann ein Wert einfach nur als Argument im nächsten Aufruf weitergegeben wird und wann im return wirklich damit gerechnet wird? Also wo genau liegt der Unterschied zwischen (zahl/10) und (zahl%10) warum wird bei zahl%10 JEDER Rest der Zahl betrachtet und warum ist zahl/10 einfach nur ein Zwischenergebnis?

 

[Gucky]

Argument: wenn es in runden Klammern steht und direkt vor den Klammern steht ein Methodenbezeichner.

Warum JEDER Rest? Ich sehe nur einen.

 

[flopalko]

Also nochmal mit einem Beispiel, also z.B 24:

1.: 22>10 -> return quersumme(24/10)+quersumme(24%10)
2.: jetzt sehen wir uns die beiden Teile nochmal an:
quersumme(24%10) = quersumme(4): 4<10 -> return 4
quersumme(24/10) = quersumme(2): 2<10 -> return 2
3.: jetzt sind wir am Ende der Rekursion angekommen und springen wieder nach oben zurück. Die aufrufende Methode hat alle Returnwerte von Methoden, die sie aufgerufen hat bekommen und kann nun selbst weiterarbeiten. Daher werden jetzt die beiden Ausdrücke (quersumme(24%10)+quersumme(24/10)) addiert und dieser Wert dann returnt.

Was du verstehen musst: es wird nur das returnt, wo davor auch ein return steht. Wenn also z.B. steht return quersumme(24%10) wird nicht das Ergebnis aus 24%10 und quersumme(24%10) returnt sondern es wird die Funktion quersumme mit dem Parameter 24%10 returnt. Kommt man nun bei diesem Parameter wieder auf keinen Returnwert sondern muss wieder quersumme mit einem weiteren Parameter ausführen, springt man halt noch eine Ebene tiefer. Dies geschieht so lange, bis man eine Abbruchbedingung erreicht hat, in unserem Fall ist dies if(zahl < 10). Passiert dies, springt man eine Ebene nach oben, addiert die beiden ausgewerteten Ausdrücke und returnt dies. Dies tut man so lange, bis man am Ausgangspunkt angekommen ist und man ist fertig.

 

[yeha]

alles klar danke