Récursion - Python, question sur la valeur renvoyée

Question

Je me rends compte que cela peut sembler une question idiote, mais la dernière fois que j'ai programmé le programme était en assembleur, ma pensée est peut-être fausse:

Une fonction récursive en tant que telle:

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

Pourquoi, lorsque la fonction atteint n == 0, elle ne renvoie pas 1 mais plutôt la réponse qui est la factorielle. Je pense quelque chose comme en assembleur ce serait quand n == 0:

mov eax, 1
ret

Pourquoi le code ci-dessus fonctionne-t-il, je suppose que python renvoie la dernière valeur de la pile avant cette condition?

Answer 1

Pensez comme ceci, pour fac (5) par exemple:

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

Donc 1 sera la première valeur renvoyée, mais sera renvoyée à fac (1) et fac (1) sera renvoyé à fac (2) et ainsi de suite.

Answer 2

Il renvoie 1 lorsque n == 0. Cette valeur de retour est extraite de la pile du site appelant, ce qui correspond à l'invocation dans n * fac (n - 1) . Ce 1 est multiplié par n et renvoyé, etc.

Answer 3

Si vous appelez fac (0), il renverra 1 (pas 0, mais je suppose que c'est juste une faute de frappe dans votre question). Si vous appelez fac (1), il ira dans la clause else et appellera fac (0) . Cela retournera 1. Il calculera ensuite n * 1, qui est 1, et le retournera. Si vous appelez fac (2) , il ira également dans la clause else, où il appellera fac (1) qui, comme mentionné ci-dessus, retournera 1, donc n * fac (n-1) sera égal à 2 et constitue la valeur de retour de fac (2) . Etc. J'espère que cela vous l'a expliqué.

Answer 4

Rien n'est implicitement renvoyé - lorsque n = 0, la fonction entre l'instruction if et renvoie 1 directement à partir de l'instruction return 1 . Cependant, ce n'est pas le point auquel la "réponse qui est la factorielle" est retourné à l'utilisateur. Au lieu de cela, il peut retourner cette valeur à la Fonction appelante appelée par fac (1), située au milieu de la branche n * fac (n - 1) . Ainsi, il faudra que le " 1 " renvoyé et renvoyé n * 1 , qui représente 1 à l'appelant . Si cela correspond à fac (2), il retournera n * 1 ou 2 à l'appelant , etc.

.

Ainsi fac (5) est traduit comme:

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

Ce n'est qu'après que la valeur 1 est renvoyée à travers chaque couche supérieure qu'elle soit renvoyée au premier appelant et que la multiplication à chaque étape vous donne la réponse.

Answer 5

James, lorsque le dernier appel de votre fonction (lorsque n == 0) est renvoyé, il ne s'agit que de l'une des instances de fac (n) sur la pile d'appels. Si vous dites print (fac (4)), la pile est essentiellement:

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

Le dernier appel à fac (0) renvoie correctement 1, mais vous avez demandé à Python la valeur de retour du premier appel à fac (n), fac (4).

Ne le considérez pas comme une boucle où "ret" va éclater, le retour conclut simplement l'une des exécutions en attente.