Rekursion Python verstehen

[Finux]

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 20. August 2019 von Finux

[Finux]

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)

[JimTheLion]

% 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 20. August 2019 von PVoss

[Gast Konketea]

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 20. August 2019 von Konketea