Factorial en programación Java

Hoy hablaremos de factoriales. Esta es una de las funciones más básicas que un programador necesita conocer y al mismo tiempo poder trabajar con ella. Entonces empecemos. El factorial de n es el valor del producto (multiplicación) de todos los números naturales del 1 al n, que se denota como n. Cómo se ve:

1! =  1
2! =  1 * 2 = 2
3! =  1 * 2 * 3 = 6
4! =  1 * 2 * 3 * 4 = 24
5! =  1 * 2 * 3 * 4 * 5  = 120

Y una pequeña regla más, para 0:

!0  = 1

Si queremos, por ejemplo, obtener la diferencia factorial 6! y 4!:

6!-4! = 1⋅2⋅3⋅4⋅5⋅6 - 1⋅2⋅3⋅4 = 720 - 24 = 696

Echemos un vistazo a cómo se vería esto en Java y comprendamos varias formas en que se puede calcular el factorial.

La solución habitual

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i;
  }
  return result;
}

Nada complicado: usamos el número recibido como el tamaño de nuestro ciclo, en el que multiplicamos por todos los números anteriores hasta llegar a f. Y en principal:

System.out.println(getFactorial(6) - getFactorial(4));

Comprobamos y obtenemos el resultado deseado: 696.

solución recursiva

La recursividad consiste en hacer algo de lógica llamando a un método sobre sí mismo. Este método se llama recursivo. Normalmente consta de dos partes:

1. condición de salida del método, al alcanzar la cual el método debería dejar de llamarse a sí mismo y comenzar a pasar valores hacia arriba. De lo contrario, obtendremos un bucle infinito al llamar a un método sobre sí mismo y, como resultado, un StackOverflowError .

2. algún procesamiento (lógica) necesario en una situación dada + llamándose a sí mismo, pero con un valor entrante diferente.

Nuestro ejemplo ideal de recursividad hoy es encontrar el factorial:

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

Establecemos la condición para salir de la recursividad cuando llega a 1. Si el argumento no es 1, multiplicamos el valor actual por el resultado de la siguiente llamada a este método (donde enviamos el valor actual -1).

Solución con Stream

Para aquellos que no conocen la funcionalidad de transmisión o para aquellos que desean refrescar la memoria, será útil leer esto .

public static int getFactorial(int f) {
  if (f <= 1) {
     return 1;
  }
  else {
     return IntStream.rangeClosed(2, f).reduce((x, y) -> x * y).getAsInt();
  }
}

Aquí utilizamos una clase especial IntStream, que proporciona capacidades adicionales cuando se trabaja con flujos a partir de valores int. Para crear dicha secuencia, usamos su método estático rangeClosed, que crea valores de 2 a f inclusive con un paso de 1. A continuación, combinamos todos los valores usando el método de reducción, es decir, mostramos en él cómo queremos combinarlos. Finalmente, obtenemos el valor resultante usando el método de terminal getAsInt.

Usando BigInteger

En Java, la clase BigInteger se usa a menudo para manejar números, especialmente números GRANDES . Después de todo, si usamos int, entonces el factorial máximo que podemos tomar sin perder datos es 31, por mucho tiempo, 39. Pero, ¿qué pasa si necesitamos un factorial de 100? Veamos las soluciones anteriores, pero usando BigInteger.

La solución habitual

public static BigInteger getFactorial(int f) {
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

El algoritmo de conteo es esencialmente el mismo, pero aquí usamos las capacidades de BigInteger: BigInteger.ONE - para establecer el valor inicial en 1. multiplicar - multiplicación entre el valor factorial anterior y el número actual.

solución recursiva

public static BigInteger getFactorial(int f) {
  if (f <= 1) {
     return BigInteger.valueOf(1);
  }
  else {
     return BigInteger.valueOf(f).multiply(getFactorial(f - 1));
  }
}

La lógica general de la solución no cambia, excepto que se agregan algunos métodos para trabajar con BigInteger.

Solución con Stream

public static BigInteger getFactorial(int f) {
  if (f < 2) {
     return BigInteger.valueOf(1);
  }
  else {
     return IntStream.rangeClosed(2, f).mapToObj(BigInteger::valueOf).reduce(BigInteger::multiply).get();
  }
}

Básicamente todo es igual, pero con BigInteger. En stream ahora tenemos el método mapToObj, con el que convertimos valores int a BigInteger para luego multiplicarlos usando multiplicar (bueno, agregamos get para tomar un objeto del contenedor Opcional ). Si ejecutamos cualquiera de estos tres métodos con el argumento 100, entonces no tendremos desbordamiento y obtendremos:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000