Factorial

Q: ¿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) .

Q: ¿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.

Q: ¿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.

PrincipianteMatemáticas y simulación Recursión

+10

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

factorial(n: integer) → integer

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.

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.

0 de 3 abiertas

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 n es 0, devuelve 1. Este es el caso base.
De lo contrario, llama a la función con n-1.
Multiplica ese resultado por n y 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 k desde 2 hasta n, ambos incluidos.
Multiplica result por k en 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 es 1.
Detener la recursión solo en n == 1. Si se llama con 0, esa función nunca llega a su caso base: continúa con -1, -2 y así sucesivamente hasta que se desborda la pila. Haz que n == 0 sea el caso base.
Usar un bucle con k < n en lugar de k ≤ n. Eso omite el último factor y devuelve (n-1)!, así que 5 da 24 en lugar de 120.
Ignorar el desbordamiento. 13! = 6227020800 no 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 hasta 20!; 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 cuando n es 0 o 1.

Preguntas frecuentes3

¿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.

def factorial(n):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

n = 5

Salida Esperada