Jump to content
  • 0

Frage

Hallo, 

als Anfänger beschäftige ich mich gerade mit der Rekursion. Was eine Rekursion ist, weiß ich, aber ich verstehe den genauen Ablauf von folgendem Code nicht. Vielleicht hat jemand die Muße mir jeden Schritt der ausgeführt wird zu verschriftlichen.. ich glaube anders verstehe ich es nicht. 

Die Funktion ist fehlerfrei, mir gehts nur ums Verständnis. 
1. Wie sieht jeder einzelne Schritt aus der durchgeführt wird + was ist im Zwischenspeicher?

2. Wofür genau brauche ich das n%10 vor dem sum_func(n//10)? (Ohne komme ich aufs falsche Ergebnis, aber wieso?)

 

Was die Funktion letztlich tut:

Übergabe von 4321 an Funktion, diese rechnet dann 4+3+2+1 und gibt 10 als Ergebnis zurück

def sum_func(n):

    if len(str(n)) == 1:
        return n

    else:
        return n % 10 + sum_func(n//10)



print(sum_func(4321))	

LG, 

Fin

 

 

P.S.: Das Debuggen hatte mir keine Erleuchtung bringen können. 

bearbeitet von Finux

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

3 Antworten auf diese Frage

Empfohlene Beiträge

  • 0

Und gerade dann doch verstanden. Danke dennoch. Ich arbeite mich fleißig vor, denn ich muss die Kleinigkeiten ja verstehen, wenn ich eine monströse Rekursionsaufgabe lösen muss. (Da werde ich dann ggfs. nochmal hier nachfragen)

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
  • 0

% ist der Modulo-Operator, der führt eine Division durch und gibt den Rest als Ergebnis zurück

// ist der abrundende Divisionsoperator

[edit]

Im Endeffekt macht n % 10 + sum_func(n//10) also nichts anderes als die letzte Stelle im Speicher zu halten und sum_func mit den vorhergehenden Stellen aufzurufen, anschließend wird die erste Stelle dann mit dem Ergebnis vom sum_func-Aufruf addiert.

  [/edit]

 

Mir fehlt gerade die Fantasie für eine bessere Darstellung deshalb...

Der rekursive Ablauf würde so aussehen:

Aufruf sum_func(4321)

  • Zeichnlänge größer 1
    • Skip If-Block
  • return 4321 % 10 [= 1] + Aufruf sum_func(4321 // 10 [432])
    • Zeichenlänge größer als 1
      • Skip If-Block
    • return 432 % 10 [= 2] +  Aufruf sum_func(432 // 10 [43])
      • Zeichenlänger größer als 1
        • Skip If-Block
      • return 43 % 10 [= 3] +  Aufruf sum_func(43 // 10 [4])
        • Zeichenlänge ist 1
          • return 4

Das ist der Stack, der dann im Endeffekt so abgearbeitet wird
 

sum_func(4)
 return 4

sum_func(43)
 return 3 + 4

sum_func(432)
 return 2 + 7

sum_func(4321)
 return 1 + 9

 

bearbeitet von PVoss

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
  • 0

Die Erklärung von @PVoss ist formal absolut korrekt. Ich möchte aber noch auf einen anderen Punkt eingehen, nämlich auf die Herangehensweise wie man Rekursionen sehr einfach abstrahieren kann. Das macht man nämlich am einfachsten Buttom Up und nicht Top Down wie oben gezeigt. Beim Buttom Up Ansatz versteht man sofort, warum der Code aussieht, wie er aussieht.

Bleiben wir mal bei dem Beispiel. Es soll eine Funktion geschrieben werden, welche die Quersumme der übergebenen Zahlen berechnet. Sprich quersumme(4321) = 4+3+2+1 = 10

Wenn man solche Aufgaben rekursiv lösen will, dann hilft der Buttom Up Ansatz. Man muss sich zunächst die Frage stellen, was der einfachste Fall wäre für einen Funktionsaufruf. Der einfachste Fall wäre, wenn ich nur die Quersumme aus einer Zahl  mit einer Ziffer berechnen wollen würde.  Spiele ich das einfach mal für mich durch:

quersumme(5) = 5
quersumme(0) = 0
quesumme(2) = 2

Tatsächlich. Die Quersumme einer übergebenen Zahl mit nur einer Ziffer ist immer die übergebene Zahl selbst. Sprich: In der Rekursion muss ich zunächst den einfachsten Fall abbilden. In dem Codebeispiel oben ist der einfachste Fall:

if len(str(n)) == 1:
        return n

Wenn n nur eine Stelle lang ist, gebe n zurück.

Wenn ich den einfachsten Fall habe, kommt der clu an der Rekursion. Jetzt muss ich mir nämlich nur noch den minimal schwierigeren Fall angucken und überlegen, wie ich vom schwierigeren Fall zum einfacheren Fall komme.

Mache ich für mich wieder die Probe:

quersumme(62) = 6+2 = 8
quersumme(77) = 7 + 7 = 14
quersumme(20) = 2 + 0 = 2

Ich kann hier folgendes ableiten: Wenn ich mehr als eine Stelle habe, dann muss ich immer die letzte Stelle n, die für sich genommen eben der einfache Fall ist (n=n) mit der nächst höheren zehner Stelle addieren und diesen Wert zurückgeben. Mit dem einfachen Fall habe ich bereits abgedeckt, dass ich die Quersumme einer ziffer berechnen kann. Was ich jetzt noch brauche ist ein zweiter Fall, in dem ich die einzelne Ziffer mit der nächst höheren zehner stelle addiere. Also nehme ich mir einmal die letzte Zahl (n % 10) und addiere sie mit der quersumme der nächsten höheren zehnerstelle. Wie bekomme ich die nächst höhere zehnerstelle? Nun ja, ich dividiere die Zahl durch 10 mit abgetrennter Kommastelle, dann habe ich ja meine zweite Zahl, und übergebe diese einfach wieder an meine Funktion. Denn wir wissen ja: Wenn ich nur eine Ziffer an meine Quersummen Funktion übergebe, bekomme ich ja schon durch den einfachsten Fall die korrekte Quersumme zurückgeliefert. Das ist genau das, was folgender Code tut:

return n % 10 + sum_func(n//10)

Bei quersumme(20) würde das also bedeuten: Addiere die letzte Ziffer (0) mit der Quersumme von (2)  =>  0 + Quersumme(2) = 2

Wenn du also auf deinen einfachsten Fall zurückgreifst durch den Funktionsaufruf, kannst du x beliebige Ziffernfolgen reinschmeißen, dein Code wird die immer richtig auflösen! Warum funktioniert das auch mit mehr als 2 Ziffern? Weil du zwei Fälle abdeckst. Einmal den Fall wo die Zahl nur eine Ziffer lang ist, und einmal den Fall wo die Zahl mehr als eine Ziffer hat.

Fazit: Wenn man sich den einfachsten Fall und den minimal komplexeren Fall anschaut und im Code abbildet, dann braucht man komplexe Funktionsaufrufe wie Quersumme(4321) nicht mehr vollständig durchdenken wie @PVoss es gemacht hat.  Und so kann man jede Rekursion abbilden. Das funktioniert praktisch immer nach dem gleichen Schema. Egal ob Quersumme, Ziffern zählen, ein String auf ein Palindrom prüfen oder oder oder ...

Und genauso kannst du auch beim lesen der Rekursion Vorgehen. Schau dir an wo der einfachste Fall abgebildet ist, verstehe ihn, und dann schau dir dann was der minimal komplexere Fall wäre und wie der abgebildet ist. Das erfordert am Anfang natürlich etwas Übung, bis man dieses Vorgehen verstanden hat und den Dreh raus hat, es erspart einem im nachhinein aber unendlich viel Zeit bei der Analyse von Rekursionen.

bearbeitet von Konketea

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
Gast
Diese Frage beantworten...

×   Du hast formatierten Text eingefügt.   Formatierung jetzt entfernen

  Only 75 emoji are allowed.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Clear editor

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.


Fachinformatiker.de, 2019 SE Internet Services

fidelogo_small.png

if_icon-6-mail-envelope-closed_314900.pnSchicken Sie uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App


Get it on Google Play

Kontakt

Hier werben?
Oder senden Sie eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...

Wichtige Information

Fachinformatiker.de verwendet Cookies. Mehr dazu in unserer Datenschutzerklärung