Fatorial em programação Java

Hoje falaremos sobre fatoriais. Esta é uma das funções mais básicas que um programador precisa conhecer e ao mesmo tempo poder trabalhar com ela. Então vamos começar. O fatorial de n é o valor do produto (multiplicação) de todos os números naturais de 1 a n, que é denotado como n! O que isso parece:

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

E mais uma pequena regra, para 0:

!0  = 1

Se quisermos, por exemplo, obter a diferença fatorial 6! e 4!:

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

Vamos dar uma olhada em como isso seria em Java e entender várias maneiras pelas quais o fatorial pode ser calculado.

A solução 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 o número recebido como tamanho do nosso ciclo, no qual multiplicamos por todos os números anteriores até chegar a f. E principalmente:

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

Verificamos e obtemos o resultado desejado: 696.

Solução recursiva

A recursão está fazendo alguma lógica chamando um método para si mesmo. Este método é chamado recursivo. Normalmente consiste em duas partes:

1. condição de saída do método, ao atingir a qual o método deve parar de se chamar e começar a passar valores. Caso contrário, obteremos um loop infinito ao chamar um método sobre si mesmo e, como resultado, um StackOverflowError .

2. algum processamento (lógica) necessário em uma determinada situação + chamada a si mesmo, mas com um valor de entrada diferente.

Nosso exemplo ideal de recursão hoje é encontrar o fatorial:

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

Definimos a condição para sair da recursão quando ela atingir 1. Se o argumento não for 1, multiplicamos o valor atual pelo resultado da próxima chamada a este método (para onde enviamos o valor atual -1).

Solução com Stream

Para quem não conhece a funcionalidade do stream ou para quem deseja refrescar a memória, será útil ler isto .

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

Aqui usamos uma classe especial IntStream, que fornece recursos adicionais ao trabalhar com fluxo de valores int. Para criar tal fluxo, usamos seu método estático rangeClosed, que cria valores de 2 a f inclusive com um passo de 1. A seguir, combinamos todos os valores usando o método de redução, ou seja, mostramos nele como queremos combiná-los. Finalmente, obtemos o valor resultante usando o método terminal getAsInt.

Usando BigInteger

Em Java, a classe BigInteger é frequentemente usada para lidar com números, especialmente números BIG . Afinal, se usarmos int, o fatorial máximo que podemos obter sem perder dados é 31, por muito tempo - 39. Mas e se precisarmos de um fatorial de 100? Vejamos as soluções anteriores, mas usando BigInteger.

A solução 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;
}

O algoritmo de contagem é essencialmente o mesmo, mas aqui usamos os recursos do BigInteger: BigInteger.ONE - para definir o valor inicial como 1. multiplicação - multiplicação entre o valor fatorial anterior e o número atual.

Solução recursiva

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

A lógica geral da solução não muda, exceto que alguns métodos para trabalhar com BigInteger são adicionados.

Solução com 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();
  }
}

Essencialmente tudo é igual, mas com BigInteger. No stream agora temos o método mapToObj, com o qual convertemos valores int em BigInteger para posteriormente multiplicá-los usando o método multiplicador (bem, adicionamos get para pegar um objeto do wrapper Opcional ). Se executarmos qualquer um desses três métodos com o argumento 100, não teremos overflow e obteremos:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000