verstehen rekursive Funktion python

Question

Ich versuche zu verstehen, was passiert, wenn diese rekursive Funktion aufgerufen wird. Der Code soll eine Spur sein

def mysum(lower, upper, margin): 
    blanks = ' ' * margin 
    print blanks, lower, upper 
    if lower > upper: 
     print blanks, 0 
     return 0 
    else: 
     result = lower + mysum(lower + 1, upper, margin + 4) 
     print blanks, result, lower, margin 
     return result 

if __name__ == "__main__": 
    mysum(1, 4, 0) 

die Ausgabe liest

1 4 
    2 4 
     3 4 
      4 4 
       5 4 
       0 
      4 4 12 
     7 3 8 
    9 2 4 
10 1 0 

Ich verstehe nicht, warum die Funktion zu entspannen beginnt, nachdem er den Wert 0 zurück Können Sie mir helfen folgen durch das, was passiert,

Answer 1

Hier ist der Code mit Kommentaren, der Ihnen hilft zu verstehen, wie die rekursive Funktion funktioniert.

def mysum(lower, upper, margin): 
    blanks = ' ' * margin  # First time : margin = 0 
           # 2nd time : margin = 4 
    print blanks, lower, upper # first time : lower = 1, upper = 4 
           # 2nd time : lower = 2, upper = 4 
    if lower > upper: # first time : go to else (& 2nd time, ... until lower =5) 
     print blanks, 0 
     return 0 
    else: 
     result = lower + mysum(lower + 1, upper, margin + 4) # result is not directly calulated 
                   # first it need to execute the call to 
                   # the function, it will be the second call 
     print blanks, result, lower, margin 
     return result 

if __name__ == "__main__": 
    mysum(1, 4, 0)  # First call of your function 

Bei niedriger bei 5 ist, gibt es keinen Aufruf mySum und es gibt 0 zurück So entspannen Sie nur einen Schritt: niedriger bei 4, und Sie, wo in der „else“ Teil. Sie haben es mit niedriger = 4 und der letzte Aufruf zurückgegeben 0. Das Ergebnis = 4.

result = lower + mysum(lower + 1, upper, margin + 4) 
print blanks, result, lower, margin 
return result 

zu beenden und Sie einen weiteren Schritt entspannen: niedriger bei 3 ist, und der Anruf kurz vor einer 4 zurückgekehrt, so Das neue Ergebnis ist 7. Dieser Wert wird zurückgegeben.

nun niedriger = 3, tun Sie das gleiche, für niedrigere = 2, untere = 1.

Sie können sehen, dass 1 + 2 + 3 + 4 = 10. Und es ist das Ergebnis Ihrer Funktion . Ich hoffe, dass ich dir geholfen habe, sag mir, wenn du es nicht verstehst, kann ich vielleicht einen anderen Weg finden, es zu erklären ...:/

Answer 2

Kurz gesagt, Sie führen immer einen rekursiven Aufruf, bevor Sie eine return Anweisung erreichen, bis Sie den Basisfall erreichen. Dann erreichen Sie immer eine return-Anweisung, bevor Sie einen weiteren rekursiven Aufruf erreichen (trivialerweise, da es nur einen rekursiven Aufruf gibt).

Answer 3

Wenn ein Aufruf der Funktion 0 ("bottoms out") zurückgibt, kann es viele weitere Aufrufe der Funktion auf dem Stapel geben, die darauf warten, fortzufahren. Wenn die Rekursion beendet ist, kehrt die Steuerung zur vorletzten Funktion auf dem Stapel zurück. Er beendet seine Arbeit und kehrt zurück, und die Steuerung kehrt zur nächsten früheren Funktion auf dem Stapel zurück. Dies wird fortgesetzt, bis alle Aufrufe an mysum aus dem Stapel entfernt wurden, in umgekehrter Reihenfolge zu der Reihenfolge, in der sie auf dem Stapel abgelegt wurden.

Vielleicht hast du all das schon verstanden :) Wenn ja, dann klär bitte was du meinst mit "warum die Funktion anfängt sich zu entspannen".

Answer 4

Ich denke, eine nützliche Beobachtung hier ist, dass die ersten fünf Zeilen gedruckt werden, bevor einer der verschachtelten Aufrufe zurückgibt. Dies alles geschieht im ersten Teil des Funktionskörpers:

print - Zustand prüfen - gehen Sie zu else - und gehen Sie zum Anfang wieder, eine Ebene tiefer.

Wenn 0 gedruckt wird, kehrt der tiefste Anruf zurück, so dass der zweittiefste result berechnet wird. Dann kommt die print aus der nächsten Zeile - und es ist die erste Zeile mit 3 Zahlen drin. Dann triffst du einen anderen return, also wird ein weiterer result berechnet usw. Die aufeinanderfolgenden Rückgaben entsprechen früheren Anrufen - also haben sie weniger blanks.