Irritiert über die Ausgabe einer Funktion

[Range]

Hallo Leute

Ich lerne gerade das Tutorial auf der seite http://www.python-kurs.eu/ . Und ich komme bei der Rekursive Funktion etwas durcheinander.
Und zwar irritiert mich die Ausgabe der Funktion.
Folgender Code....

Code: Alles auswählen

def factorial(n):
    print("factorial has been called with n = " + str(n))
    if n == 1:
        return 1
    else:
        res = n * factorial(n-1)
        print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res)
        return res	

print(factorial(5))

gibt folgender Ausgabe:

Code: Alles auswählen

factorial has been called with n = 5
factorial has been called with n = 4
factorial has been called with n = 3
factorial has been called with n = 2
factorial has been called with n = 1
intermediate result for  2  * factorial( 1 ):  2
intermediate result for  3  * factorial( 2 ):  6
intermediate result for  4  * factorial( 3 ):  24
intermediate result for  5  * factorial( 4 ):  120
120

Für meinen Verständniss erwarte ich, dass der Code zuerst wie schon richtig der ersten print(factorial has been called with n = 5) aufruft. Aber dann dachte ich mir sollte der Zweiten print(intermediate result for 2 * factorial( 1 ): 2) aufgerufen werden. Und dann wieder zur Anfang... Und so weiter..
Das heisst:
1. print("factorial has been called with n = " + str(n)) wird ausgewärtet und ausgegeben.
2. Da Parameter Wert nicht gleich 1 ist, wird else aufgerufen: Und die Variable res = n * factorial(n-1) ausgewärtet.
3. print("intermediate result for ", n, " * factorial(" ,n-1, "): ",res) wird ausgewärtet und ausgegeben.
4. Schliesslich wird durch return res die gesammte Funktion mit (n-1) widerhollt.
Dem ist aber nicht so, und ich verstehe nicht warum. Wo habe ich etwas falsch verstanden??

Vielen dank schon mal

[Hyperion]

Guck Dir den Ablauf noch einmal genau an! Zeile 6 ist dabei entscheindend

[Range]

Danke schon mal für die schnelle Antwort.

Bei Zeile 6 wird ja nur die variable res definiert. Hier findet die Rekursion noch nicht statt, oder doch??

Ich dachte erst mit 'return res' wird die Rekursion gestartet, und somit die Funktion wiederhollt.

[Sr4l]

In der Zeile 6 wird nicht nur eine Variable definiert, sondern auch eine Funktion aufgerufen. Das ist entscheidend.

*edit* Durch den Aufruf der Funktion läuft der Programmcode nicht weiter ab, sondern arbeitet erstmal die gerade aufgerufen Funktion ab.

[/me]

Ich dachte erst mit 'return res' wird die Rekursion gestartet, und somit die Funktion wiederhollt.

Ein return ist dazu da einen Wert aus einer Funktion zurückzugeben. Das hat mit Rekursion erst einmal nichts zu tun.

Hier ist ein ganz simples Beispiel für Rekursion das den Rückgabewert komplett ignoriert.

Code: Alles auswählen

def work(value):
    if value > 0:
        print(value)
        work(value - 1)

[snafu]

@Range: Du hast offenbar Rekursion noch nicht ganz verstanden. Die Rekursion geschieht in dem Moment, wo die Funktion sich selbst aufruft.

`return` hat damit nichts zu tun. Es wird nur dazu verwendet, die Resultate der rekursiven Funktionsaufrufe zu liefern, um am Ende des Rekursionsverlaufs ein Gesamtergebnis zu haben. Die Rekursion an sich wird dadurch nicht beeinflusst.

Es gibt keinen eingebauten "Rekursionsmodus", der Python dazu veranlasst, auf magische Weise zu erkennen, dass Code an einer bestimmten Stelle verzögert ausgeführt werden soll. Python führt stumpf das aus, was in der Funktion definiert worden ist.

Daraus folgt: Du hast definiert, dass die zweite Meldung immer erst nach dem rekursiven Aufrufen der Funktion erscheint. Das macht ja auch Sinn, da die Meldung das Ergebnis dieses Aufrufs beinhaltet. Das Ergebnis kann aber nur ermittelt werden, wenn die Funktion auch tatsächlich erneut mit den neuen Parametern ausgeführt wird. Da zu Beginn der Funktion jedoch definiert wurde, dass die erste Meldungsart angezeigt wird, kommt es logischerweise wieder zur Ausgabe der ersten Meldung. Nun soll diese Funktion wieder die zweite Meldung ausgeben, kann dies aber erst nach einem erneuten rekursiven Aufruf tun, usw.

Erkennst du, worauf das hinausläuft?

EDIT: Mach dir einfach bewusst, dass der erste Funktionsaufruf erst zum Ergebnis kommen kann, wenn er "weiß", was der zweite Funktionsaufruf als Ergebnis ermittelt hat. Und zweite weiß es erst dann, wenn der dritte ein Ergebnis hat, usw.

[Range]

Erstmal vielen Dank allen für die vielen Antworten.

In der Zeile 6 wird nicht nur eine Variable definiert, sondern auch eine Funktion aufgerufen. Das ist entscheidend.

Hier habe ich wohl das entscheidende fehler gemacht. Ich wusste nicht, dass bei der definition von 'res' die Funktion wieder aufgerufen wird. Sondern erst mit 'return res'. Übrigens weiss ich schon, dass return nichts mit der Rekursion zutun hat. Ich verwies nur auf die Variable 'res', die die Rekursion in sich trägt. Aber jetzt weiss ich ja, dass das ein grober Denkfehler war.
Eins verstehe ich aber noch nicht. Warum beginnt die Berechnung dann am schluss?
Also...
intermediate result for 2 * factorial( 1 ): 2
intermediate result for 3 * factorial( 2 ): 6
intermediate result for 4 * factorial( 3 ): 24
intermediate result for 5 * factorial( 4 ): 120
und nicht..
intermediate result for 5 * factorial( 4 ): 120
intermediate result for 4 * factorial(3): 24
intermediate result for 3 * factorial( 2 ): 6
intermediate result for 2 * factorial(1): 2

[/me]

Warum beginnt die Berechnung dann am schluss?

Da ist die Frage wie du "Schluss" definierst. Für mich beginnt sie am Anfang.

Bevor du die 120 berechnest musst du ja erst die 24 haben. Davor die 6 und davor die 2. Genau das macht ja der von dir gezeigte Code. Die Funktion ruft sich selber so oft auf bis sie an der Abbruchbedingung (n == 1) angekommen ist. Dann steigt sie über die gesamte Aufrufhierarchie quasi wieder nach oben und führt dabei die Berechnungen durch. Noch mal: In der Zeile res = n * factorial(n-1) wird zuerst factorial(n - 1) ausgeführt und erst wenn das erledigt und zurückgekommen ist, dann kommt die Multiplikation mit n.

Solltest du übrigens jemals bei einem Test zeigen müssen wie du die Fakultät berechnest, dann verwende auf keinen Fall einen rekursiven Aufruf. Fakultätsberechnung ist zwar sehr schön um Rekursion zu zeigen, aber grundsätzlich eine denkbar schlechte Lösung für diese Aufgabe.

Hier sind zwei andere Arten die Fakultät zu berechnen. Zumindest die erste sollte klar sein.

Code: Alles auswählen

result = 1
for value in range(1, 6):
    result *= value
print(result)

import functools
import operator
print(functools.reduce(operator.mul, range(1, 6)))

[snafu]

@Range: Der innerste Funktionsaufruf kommt halt als erstes zu einem Ergebnis und kann folglich in seinem Ablauf als erstes eine Ausgabe ins Terminal schreiben. Dann gibt er dieses nochmal als Zahl zurück und der vorherige Aufruf hat wieder die Kontrolle. Der benutzt das Ergebnis, macht damit seine Multiplikation und erledigt dann die Ausgabe "seiner" Meldung, usw.

[Range]

Da ist die Frage wie du "Schluss" definierst. Für mich beginnt sie am Anfang.

Naja zuerst kommt ja der Parameter '5', und bei jeder weitere Aufruf entsprechend 4,3,2. Dann würde ich ja denken, dass bei Abbruchbedienung, nun die Berechnung auch nach dieser Reihenfolge stattfinden würde.

Dann steigt sie über die gesamte Aufrufhierarchie quasi wieder nach oben und führt dabei die Berechnungen durch.

Genau das meinte ich. Vielen Dank

[Range]

Der innerste Funktionsaufruf kommt halt als erstes zu einem Ergebnis und kann folglich in seinem Ablauf als erstes eine Ausgabe ins Terminal schreiben. Dann gibt er dieses nochmal als Zahl zurück und der vorherige Aufruf hat wieder die Kontrolle. Der benutzt das Ergebnis, macht damit seine Multiplikation und erledigt dann die Ausgabe "seiner" Meldung, usw.

@snafu
Das hast du für einen Laien wie mich sehr gut erklärt danke.

[Hyperion]

Ich wusste nicht, dass bei der definition von 'res' die Funktion wieder aufgerufen wird.

Man spricht in Python auch nicht von Definition; man sagt eher "``res`` wird an etwas gebunden".

Ich weiß nicht, ob es so explizit schon gesagt wurde, aber ich mach es trotzdem noch mal: Weder ``return`` noch das Binden an einen Wert bewirken einen Funktionsaufruf, sondern "der Aufruf" selber, eben das "Funktionsname + runde Klammer auf + evtl. Parameter + runde Klammer zu". Bei Dir eben das ``factorial(n-1)``. Genau *das* ruft eben die Funktion ``factorial`` auf - *egal*, ob die Rückgabe verwendet oder zurückgegeben wird. (/me hatte dafür ja ein schönes Beispiel gegeben!)