Calcule Factorial con Java - Iterativo y Recursivo

En este artículo aprenderás a calcular el factorial de un número entero con Java, usando bucles y recursividad.

Introducción

Calcular un factorial de un número es una tarea sencilla. Un factorial de un número es el producto de ese número (entero positivo) y todos los enteros positivos menores que ese número. En otras palabras, multiplicar un número por todos los números enteros desde ese número hasta 1.

0! también es igual a 1, ya que no puedes exactamente pasar de 0 a 1.

Es simplemente un acuerdo que 0! es igual a 1, y una explicación común de esto (lamentablemente no atribuible a una sola persona) es: 'Porque hay exactamente una forma de hacer nada.'

Un factorial se denota con un número entero y va seguido de un signo de exclamación.

5! denota un factorial de cinco. Alternativamente, puede simplemente decir cinco factorial.

Y para calcular ese factorial, multiplicamos el número por cada número entero positivo menor que él:

$$
5! = 5 * 4 * 3 * 2 * 1
5! = 120
$$

En este tutorial, aprenderemos cómo calcular un factorial de un número entero en Java. Esto se puede hacer usando bucles o recursión, aunque podría decirse que la recursión es un enfoque más natural. Por supuesto, debe implementar el que le resulte más cómodo.

Cálculo factorial usando bucles

Comencemos calculando factoriales usando bucles: while y for. También podemos usar bucles do-while, pero el bloque inicial do no hace mucho por nosotros aquí e introduciría un caso extremo erróneo potencial, por lo que lo omitiremos.

El proceso general es bastante similar para ambos tipos de bucle: todo lo que necesitamos es un parámetro como entrada y un contador para iterar sobre los números.

Empecemos con el bucle for:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public static int getFactorialForLoop(int n) {
    int result = 1;
    if (n > 1) {
        for (int i = 1; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
    else {
        System.out.println("n has to be positive");
        return result;
    }
}

De hecho, nos hemos desviado un poco de la definición original aquí: estamos contando desde 1 hasta n, mientras que la definición de factorial era desde el número dado hasta 1.

Sin embargo, cuando lo pones en papel, matemáticamente:

$$
1 * 2 * 3 * 4 ... * n = n * (n-1) * (n-2) * (n-3) * (n-4) .. * (n - (n-1))
$$

Estas son declaraciones iguales, y realmente puedes pasar de 1 a n, o al revés.

Para simplificar, (n - (n-1)) siempre será igual a 1.

Eso significa que no importa en qué dirección estemos iterando. Puede comenzar desde 1 y aumentar hacia n, o puede comenzar desde n y disminuir hacia 1.

¿Por qué?

Bueno, si giras el ciclo al revés, el método no se vuelve mucho más complicado, pero es un poco menos limpio:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public static int getFactorialForLoop(int n) {
    int result = n;
    if (n >= 1) {
        for (int i = n-1; i >= 1; i--) {
            result = result * i;
        }
        return result;
    }
    else {
        System.out.println("n has to be positive");
        return 1;
    }
}

Ahora que eso está aclarado, comencemos a desglosar el método.

Toma un parámetro, n, que denota el número para el que estamos calculando un factorial. Primero, definimos una variable llamada resultado y le asignamos 1 como valor.

¿Por qué asignar 1 y no 0?

Si tuviéramos que asignarle 0, todas las siguientes multiplicaciones contendrían ese 0. Naturalmente, colapsaría toda la operación a un enorme 0.

Luego comenzamos nuestro bucle for definiendo i como el contador que comienza desde 1. Tenga en cuenta que la declaración de la condición es i <= n; para incluir también la propia n.

Dentro del ciclo for, multiplicamos el valor actual de resultado con el valor actual de nuestro índice i.

Finalmente, devolvemos el valor final del resultado. Para obtener información del usuario, recuerde importar java.util.Scanner.

If you'd like to read more about getting user input in Java - read our Guía de la clase Scanner.

Probemos nuestro método e imprimamos los resultados:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
Scanner scanner = new Scanner(System.in);
int inp;
        
System.out.println("Enter a number: "); 
inp = Integer.parseInt(scanner.nextLine());   
           
System.out.println("The result is: " + getFactorialForLoop(inp));        

    
public static int getFactorialForLoop(int n) {
    int result = 1;
    if (n >= 1) {
        for (int i = 1; i <= n; i++) {
            result = result * i;
        }
        return result;
    }
    else {
      System.out.println("n has to be positive");
      return result;
    }

Le pedirá al usuario que dé su entrada. Lo intentaremos con 4:

1
2
Enter a number: 4
The result is: 24

Puedes usar una calculadora para verificar el resultado:

4! es 4 * 3 * 2 * 1, lo que da como resultado 24.

Ahora veamos cómo podemos calcular el factorial usando el bucle while. Aquí está nuestro método modificado:

1
2
3
4
5
6
7
8
public static int getFactorialWhileLoop(int n){
    int result = 1;
    while (n > 1) {
        result = result * n;
        n -= 1;
    }
    return result;
}

Esto es bastante similar al bucle for. Excepto que, esta vez nos movemos de n hacia 1, más cerca de la definición matemática. Probemos nuestro método:

1
2
3
4
System.out.println("Enter a number: "); 
inp = Integer.parseInt(scanner.nextLine());   
    
System.out.println("The result is: " + getFactorialWhileLoop(inp));   

Introduciremos 4 como entrada una vez más:

1
2
Enter a number: 4
The result is: 24

Aunque el cálculo fue 4*3*2*1, el resultado final es el mismo que antes.

Ahora echemos un vistazo a cómo calcular el factorial usando un método recursivo.

Cálculo factorial mediante recursión

Un método recursivo es un método que se llama a sí mismo y finaliza las llamadas dada alguna condición.

En general, todo método recursivo tiene dos componentes principales: un caso base y un paso recursivo.

Los casos base son las instancias más pequeñas del problema. Además, deben tener un descanso, un caso que devolverá un valor y saldrá de la recursividad. En términos de métodos factoriales, el caso base es cuando devolvemos el elemento final del factorial, que es 1.

Sin un caso base o con un caso base incorrecto, su método recursivo puede ejecutarse infinitamente, provocando un desbordamiento.

Pasos recursivos: como su nombre lo indica, son la parte recursiva del método, donde todo el problema se transforma en algo más pequeño. Si el paso recursivo no logra reducir el problema, entonces nuevamente la recursividad puede ejecutarse infinitamente.

Considere la parte recurrente de los factoriales:

  • 5! es 5 * 4 * 3 * 2 * 1.

Pero también sabemos que:

  • 4! es 4 * 3 * 2 * 1.

En otras palabras, 5! es 5 * 4! y 4! es 4 * 3! y así sucesivamente.

Entonces podemos decir que n! = n * (n-1)!. ¡Este será el paso recursivo de nuestro factorial!

Una recursividad factorial termina cuando llega a 1. Este será nuestro caso base. Devolveremos 1 si n es 1 o menos, cubriendo la entrada cero.

Echemos un vistazo a nuestro método factorial recursivo:

1
2
3
4
5
6
7
8
public static int getFactorialRecursively(int n){
    if (n <= 1){
        return 1;
    }
    else {
        return n * getFactorialRecursively(n-1);
    }
}

Como puede ver, el bloque if encarna nuestro caso base, mientras que el bloque else cubre el paso recursivo.

Probemos nuestro método:

1
2
3
4
System.out.println("Enter a number: "); 
inp = Integer.parseInt(scanner.nextLine());   
    
System.out.println("The result is: " + getFactorialRecursively(inp)); 

Introduciremos 3 como entrada esta vez:

1
2
Enter a number:3
The result is: 6

Obtenemos el mismo resultado. Pero esta vez, lo que pasa bajo el capó es bastante interesante:

Verá, cuando ingresamos la entrada, el método verificará con el bloque si, y dado que 3 es mayor que 1, saltará al bloque else. En este bloque, vemos la línea return n * getFactorialRecursively(n-1);.

Sabemos el valor actual de n por el momento, es 3, pero getFactorialRecursively(n-1) todavía está por calcular.

Luego, el programa llama al mismo método una vez más, pero esta vez nuestro método toma 2 como parámetro. Verifica el bloque if y salta al bloque else y nuevamente se encuentra con la última línea. Ahora, el valor actual de n es 2 pero el programa todavía debe calcular getFactorialRecursively(n-1).

Entonces llama al método una vez más, pero esta vez el bloque if, o más bien, la clase base logra devolver 1 y sale de la recursividad.

Siguiendo el mismo patrón hacia arriba, devuelve el resultado de cada método, multiplicando el resultado actual con la n anterior y devolviéndolo por la llamada al método anterior. En otras palabras, nuestro programa primero llega al final del factorial (que es 1), luego va aumentando, mientras se multiplica en cada paso.

También eliminando el método de la pila de llamadas uno por uno, hasta que se devuelva el resultado final de n * (n-1).

Por lo general, así es como funcionan los métodos recursivos. Algunos problemas más complicados pueden requerir recursiones más profundas con más de un caso base o más de un paso recursivo. ¡Pero por ahora, esta simple recursión es lo suficientemente buena para resolver nuestro problema factorial!

Cálculo factorial para números grandes

Los factoriales crecen bastante rápido. Todo el mundo sabe cómo las exponenciales tienden a volverse enormes dado un pequeño número de pasos:

$$
2^6 = 64
$$

$$
6! = 720
$$

De hecho, un factorial de solo 20 es igual a:

$$
20! = 2.432.902.008.176.640.000
$$

Eso es 2,4 quintillones. El siguiente factorial es 51 quintillones, que está fuera de rango incluso para longs en Java, que se sitúa en ~9 quintillones. Los números enteros se agotan en solo ** 2.4 mil millones **, por lo que están fuera de discusión bastante rápido.

Aquí es donde entra en juego un BigInteger: la JVM no asigna previamente el espacio conocido para el número y actualiza dinámicamente su tamaño. Puede llenar toda la RAM con dígitos para un BigInteger y solo entonces se encontrará con el límite:

1
2
3
4
5
6
7
8
public static BigInteger getFactorialRecursively(int n) {
    BigInteger value = BigInteger.valueOf(n);
    if (value == BigInteger.ZERO) {
        return BigInteger.ONE;
    } else {
        return value.multiply(getFactorialRecursively(n - 1));
    }
}

Introducir 21 en este método daría como resultado:

1
51090942171709440000

Conclusión

En este artículo, cubrimos cómo calcular factoriales usando bucles for y while. También aprendimos qué es la recursión y cómo calcular el factorial usando la recursión.