Rekursion - Python, Rückgabewert Frage

Question

Ich weiß, dass dies wie eine dumme Frage klingen mag, aber das letzte Mal, dass ich es in Assembler programmiert war, so kann mein Denken aus sein:

Eine rekursive Funktion als so:

def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n - 1)

Warum ist es, dass, wenn die Funktion n == 0 erreicht, dass es nicht zurück 1, sondern die Antwort, die die Fakultät ist. Ich denke so etwas wie in Assembler wäre es, wenn n == 0:

mov eax, 1
ret

Warum den obigen Code funktioniert, nehme ich an Python den letzten Wert auf dem Stapel zurück vor diesem Zustand?

Answer 1

Denken Sie darüber nach, wie diese, für fac(5) zum Beispiel:

return 5 * fac(4)
           return 4 * fac(3)
                      return 3 * fac(2)
                                 return 2 * fac(1)
                                            return 1 * fac(0)
                                                       1

So 1 wird die zuerst Wert zurückgegeben, aber es wird zurückgegeben werden, um fac(1) und fac(1) zurückgegeben werden, um fac(2) und so weiter.

Answer 2

Es funktioniert Rückkehr 1, wenn n == 0. Das Wert zurückgeben wird, um den Stapel von der rufenden Seite taucht ab, die der Aufruf an n * fac(n - 1) war. Die 1 wird durch n multipliziert und zurückgegeben, etc.

Answer 3

Wenn Sie fac aufrufen (0) es wird wieder 1 (nicht 0 ist, aber ich denke, das ist nur ein Tippfehler in Ihrer Frage). Wenn Sie fac nennen (1), wird es in der else-Klausel gehen, und es wird es fac(0) nennen. Dies wird wieder 1. Es wird dann n * 1, berechnen, die gleich 1 ist, und zurück, dass. Wenn Sie fac(2) nennen wird es auch in der else-Klausel gehen, wo es fac(1) nennen, die wie oben erwähnt gibt 1 zurück, so wird n*fac(n-1) sein 2 und das ist der Rückgabewert von fac(2). Und so weiter. Ich hoffe, dass es für Sie erklärt.

Answer 4

Nichts ist wird implizit zurück - wenn n = 0, wird die Funktion der if-Anweisung eingeben und 1 direkt aus der return 1 Anweisung zurück. Dies ist jedoch nicht der Punkt, an dem die „Antwort, die die Fakultäts ist“ an den Benutzer zurückgegeben. Stattdessen kann sie diesen Wert auf das zurückkommen Aufruf Funktion von fac aufgerufen (1), die in der Mitte des n * fac(n - 1) Zweig. So wird es dauern, die „1“ zurück und zurück n*1, die 1 bis ist es Anrufer. Wenn das FAC (2), es wird n * 1 zurückzukehren, oder 2 bis es Anrufer und so weiter.

So fac (5) wird übersetzt wie:

fac(5) = 5 * fac(4) = 5 * (4 * fac(3) = 5 * (4* (3 * fac(2)) = 5 * (4* (3 * (2 * fac(1)) = 5 * (4* (3 * (2 * (1 * fac(0)) = 5*4*3*2*1*1

Erst nach dem 1-Wert wird durch jede obere Schicht kehrt er zurück zum ersten Anrufer erhält, und die Multiplikation in jeder Stufe gibt Ihnen die Antwort.

Answer 5

James, wenn der letzte Aufruf an der Funktion (wenn n == 0) gibt es nur einen von mehreren Instanzen von fac (n) auf dem Call-Stack. Wenn Sie drucken sagen (fac (4)), der Stapel ist im Wesentlichen:

fac(0)
fac(1)
fac(2)
fac(3)
fac(4)
print()

Der letzte Aufruf von fac (0) in geeigneter Weise 1 zurückkehrt, aber in Python haben Sie den Rückgabewert des ersten Aufrufs von fac (n) angefordert, fac (4).

Sie denken es nicht als eine Schleife, wobei ‚ret‘ ausbrechen wird, einfach die Rückkehr eines von mehreren anstehenden Hinrichtungen abschließend.