Recursión - Python, pregunta de valor de retorno

Question

Me doy cuenta de que esto puede sonar como una pregunta tonta, pero la última vez que lo programé fue en el ensamblador, por lo que mi pensamiento puede estar apagado:

Una función recursiva así:

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

¿Por qué cuando la función alcanza n == 0 no devuelve 1 sino la respuesta que es factorial? Estoy pensando que algo así como en ensamblador sería cuando n == 0:

mov eax, 1
ret

¿Por qué funciona el código anterior, supongo que python devuelve el último valor en la pila antes de esa condición?

Answer 1

Piensa en esto, por ejemplo, para fac (5) :

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

Entonces 1 será el valor devuelto por first pero se devolverá a fac (1) y fac (1) se devolverá a fac (2) y así sucesivamente.

Answer 2

Hace devuelve 1 cuando n == 0. Ese valor de retorno se saca de la pila del sitio de llamada, que era la invocación en n * fac (n - 1) . Ese 1 se multiplica por n y se devuelve, etc.

Answer 3

Si llama a fac (0) devolverá 1 (no 0, pero supongo que eso es solo un error tipográfico en su pregunta). Si llama a fac (1), irá en la cláusula else, y allí llamará a fac (0) . Esto devolverá 1. Luego calculará n * 1, que es 1, y devolverá eso. Si llama a fac (2) , también irá en la cláusula else, donde llamará a fac (1) que, como se mencionó anteriormente, devolverá 1, por lo que n * fac (n-1) será 2 y ese es el valor de retorno de fac (2) . Y así. Espero que te lo haya explicado.

Answer 4

No se devuelve implícitamente nada: cuando n = 0, la función ingresa la instrucción if y devuelve 1 directamente desde la declaración return 1 . Sin embargo, este no es el punto en el que la respuesta " que es el factorial " se devuelve al usuario. En su lugar, puede estar devolviendo este valor al Función de llamada invocada por fac (1), que se encuentra en medio de la rama n * fac (n - 1) . Por lo tanto, tomará el " 1 " devuelto y devolver n * 1 , que es 1 a es llamante. Si eso es fac (2), devolverá n * 1 , o 2 a es llamador y así sucesivamente.

Así, fac (5) se traduce como:

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

Solo después de que el valor 1 se devuelve a través de cada capa superior, vuelve al primer interlocutor, y la multiplicación en cada etapa te da la respuesta.

Answer 5

James, cuando la última llamada a tu función (cuando n == 0) regresa es solo una de varias instancias de fac (n) en la pila de llamadas. Si dice imprimir (fac (4)), la pila es esencialmente:

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

La llamada final a fac (0) devuelve adecuadamente 1, sin embargo, en Python ha solicitado el valor de retorno de la primera llamada a fac (n), fac (4).

No piense en ello como un bucle en el que 'ret' se romperá, el retorno simplemente concluye una de varias ejecuciones pendientes.