Factorial
El factorial de un número entero no negativo n, escrito n!, es el producto de todos los números enteros desde 1 hasta n. Por ejemplo, 4! = 1 × 2 × 3 × 4 = 24. Por definición, 0! = 1. Tu función recibe n y devuelve n!.
Función
- ninteger
- el número entero cuyo factorial calculas
- Devuelveinteger
- el producto de todos los números enteros del 1 al n, que es 1 cuando n es 0
Restricciones
0 ≤ n ≤ 12- La respuesta cabe en un entero con signo de 32 bits: el mayor es
12! = 479001600.
Ejemplos
- Entrada
- n = 5
- Salida
- 120
- Explicación
- Multiplica
1 × 2 × 3 × 4 × 5. El producto acumulado va por 1, 2, 6, 24 y termina en 120.
- Entrada
- n = 0
- Salida
- 1
- Explicación
- No hay nada que multiplicar, y un producto sin factores es
1. Por eso,0! = 1.
+11 pruebas ocultas al enviar
Para ir más allá
100! tiene 158 dígitos. ¿Puedes contar cuántos ceros tiene al final sin calcularlo?
Pistas
Ábrelas de una en una. Cada una revela un poco más.
Escribe
4!y5!como productos. ¿Qué relación hay entre5!y4!?5! = 5 × 4!. En general,n! = n × (n-1)!, y la cadena termina en0! = 1.Mantén un producto acumulado que empiece en
1y multiplícalo por cada número desde2hastan. Empezar en 1 también da la respuesta correcta para0y1.
Solución
El factorial tiene dos descripciones equivalentes, y cada una se convierte en código. Como producto, n! = 1 × 2 × ... × n, que es un bucle. Como definición recursiva, 0! = 1 y n! = n × (n-1)!, que es una función que se llama a sí misma. Ambas realizan aproximadamente n multiplicaciones. El bucle es la opción con la que conviene quedarse, porque no necesita una pila de llamadas.
Recursión a partir de la definición
Intuición
El factorial se define mediante un factorial más pequeño: n! = n × (n-1)!. Si ya sabes que 4! = 24, entonces 5! = 5 × 24 = 120. Una función recursiva escribe esa oración como código. Para obtener factorial(n), solicita factorial(n-1) y multiplica la respuesta por n.
Las llamadas necesitan un punto de detención, el caso base: factorial(0) devuelve 1 sin llamar a nada. Cada llamada reduce n en uno, así que, desde 5, las llamadas siguen la secuencia 5, 4, 3, 2, 1, 0. Después, las respuestas vuelven por la cadena: 1, 1, 2, 6, 24, 120.
Hay n + 1 llamadas y n multiplicaciones, así que el tiempo es O(n). Cada llamada espera en la pila hasta que la llamada inferior devuelve un resultado, así que la pila contiene n + 1 marcos, lo que ocupa un espacio de O(n). Con n ≤ 12, eso es insignificante, pero el mismo patrón con una entrada grande desborda la pila.
Algoritmo
- Si
nes0, devuelve1. Este es el caso base. - De lo contrario, llama a la función con
n-1. - Multiplica ese resultado por
ny devuélvelo.
def factorial(n):
if n == 0:
return 1 # base case: 0! = 1
return n * factorial(n - 1)Multiplicar en un bucle
Intuición
Desarrolla la recursión y obtendrás un producto acumulado. Empieza con result = 1 y multiplícalo por 2, después por 3, y así sucesivamente hasta n. Para n = 5, el resultado va siendo 1, 2, 6, 24, 120.
Empezar en 1 también cubre las entradas más pequeñas. Para n = 0 y n = 1, el bucle de 2 a n se ejecuta cero veces y la función devuelve el valor inicial 1, que es la respuesta correcta en ambos casos.
El bucle realiza n-1 multiplicaciones, tarda O(n) y ocupa O(1) espacio al guardar un solo número. No hay una pila de llamadas que pueda desbordarse, por eso los entrevistadores esperan esta versión una vez que has mostrado la recursiva.
Algoritmo
- Establece
result = 1. - Recorre
kdesde2hastan, ambos incluidos. - Multiplica
resultporken cada paso. - Devuelve
result.
def factorial(n):
result = 1
for k in range(2, n + 1):
result *= k
return result
Errores comunes y casos límite
El código del factorial es corto, así que los errores están en los casos límite.
- Empezar el producto en
0. Cada multiplicación lo mantiene en 0. El valor inicial de un producto es1. - Detener la recursión solo en
n == 1. Si se llama con0, esa función nunca llega a su caso base: continúa con -1, -2 y así sucesivamente hasta que se desborda la pila. Haz quen == 0sea el caso base. - Usar un bucle con
k < nen lugar dek ≤ n. Eso omite el último factor y devuelve(n-1)!, así que5da 24 en lugar de 120. - Ignorar el desbordamiento.
13! = 6227020800no cabe en un entero con signo de 32 bits. En Java y C#, el producto se desborda silenciosamente y da un número incorrecto; en C, el desbordamiento de enteros con signo tiene un comportamiento indefinido, y una compilación de depuración de Rust genera un pánico. Un entero de 64 bits admite hasta20!; para valores mayores necesitas enteros grandes. - En Swift, escribir
for k in 2...n. Un rango cerrado cuyo límite final es menor que el inicial provoca un fallo en tiempo de ejecución cuandones 0 o 1.
Preguntas frecuentes4
¿Cuál es la complejidad temporal de calcular un factorial?
Tanto el bucle como la recursión realizan una multiplicación por cada número hasta n, así que el tiempo es O(n). El bucle necesita un espacio extra de O(1). La recursión mantiene un marco de pila por llamada hasta que se devuelve el caso base, así que usa un espacio de O(n).
¿Por qué 0! es igual a 1?
0! es el producto de ningún número, y un producto sin factores es 1, del mismo modo que una suma sin términos es 0. También mantiene verdadera la regla n! = n × (n-1)! para n = 1: 1! = 1 × 0! = 1. El conteo coincide: hay exactamente una manera de ordenar cero elementos.
¿Es mejor la recursión o un bucle para calcular el factorial?
Realizan las mismas multiplicaciones y devuelven la misma respuesta. La versión recursiva se lee como la definición matemática, por eso es un ejercicio clásico para empezar con la recursión. El bucle usa memoria constante y no puede desbordar la pila de llamadas, así que es la mejor opción en código real.
¿Cuál es el mayor factorial que cabe en un entero?
12! = 479001600 es el factorial más grande que cabe en un entero con signo de 32 bits. 20! = 2432902008176640000 es el más grande para un entero con signo de 64 bits. Para valores mayores, necesitas números de tamaño ilimitado, como int de Python, BigInteger de Java o BigInt de JavaScript.
Problemas similares
Problemas que usan las mismas ideas. Resolver dos o tres es lo que fija un patrón.
Python
def factorial(n):
# Escribe el código aquíCaso 1
Caso 2
Entrada
n = 5
Esperado
120