Comprensión de la recursión factorial.

Estoy mirando el ejemplo factorial de recursión y me gustaría asegurarme de que lo estoy entendiendo correctamente.

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

¿Estaría en lo cierto al decir:

factorial (4) = factorial (4-1) * 4 = factorial (3-1) * 3 * 4 = factorial (2-1) * 2 * 3 * 4 = factorial (1-1) * 1 * 2 * 3 * 4 = 24

porque factorial (1-1) = factorial (0) que como el caso base muestra = 1 y luego multiplicamos por 2, luego 3 y luego 4.

¿Es esa la forma correcta de verlo?

¡Gracias por adelantado!

Sí lo es. Pero como es recursiva, funciona de manera opuesta. Una vez un entrevistador me lo explicó así:

Digamos, de hecho (5):

  - fact(5) = 5 * fact(4) - fact(4) = 4 * fact(3) - fact(3) = 3 * fact(2) - fact(2) = 2 * fact(1) - fact(1) = 1 * fact(0) - fact(0) = 1 // This is where your condition returns 1. 

Ahora, imagina que el signo de arriba representa una devolución. Básicamente devuelves lo que está después del signo - . Así que desde la línea más baja, se devuelve 1. Entonces, has devuelto 1 de hecho (1), es decir, 1 * 1. Así sucede en una cascada REVERSA como:

  = 120 - fact(5) = 5 * 24 - fact(4) = 4 * 6 = 24 - fact(3) = 3 * 2 = 6 - fact(2) = 2 * 1 = 2 - fact(1) = 1 * 1 = 1 - fact(0) = 1 

Recuerda que siempre que trabajas en recursión, todo funciona de manera inversa. Eso realmente debería ayudarte a resolver cualquier problema de recursión.

Esta es la razón por la cual la recursión de la cola y la optimización relacionada son tan importantes. En la memoria, cada una de esas llamadas se retrasa y no puede regresar hasta que las llamadas arriba (abajo en el diagtwig) terminen y regresen. Por lo tanto, una llamada recursiva muy profunda puede provocar un desbordamiento de stack a menos que el comstackdor / intérprete optimice esto convirtiéndolo en la versión en el OP, de manera que los resultados parciales se evalúen de inmediato y no se retrasen. Python no realiza esta optimización y, por lo tanto, debes tener cuidado con tus llamadas recursivas.

Sí, la forma en que lo has descrito es lo que está sucediendo.

Un punto a tener en cuenta con su código, si ingresa un valor no entero para n o un valor de n menor que 0, parece que estará atrapado en un bucle infinito.

Podría valer la pena agregar un cheque en su código para esto:

 if not isinstance(n, int): return None elif n < 0: return None 

Esto puede ser útil

 (factorial 4) (4 * (factorial 3)) (4 * (3 * (factorial 3))) (4 * (3 * (2 * (factorial 1)))) (4 * (3 * (2 * 1))) (4 * (3 * 2)) (4 * 6) (24)