Factorielle en Java

Aujourd'hui, nous allons parler des factorielles et des moyens les plus courants de trouver la factorielle Java (factorial). C'est l'une des fonctions les plus élémentaires qu'un programmeur doit à la fois connaître et être en mesure d'utiliser. Très bien, commençons. La factorielle du nombre n, indiquée comme n!, est la valeur du produit (multiplication) de tous les nombres naturels de 1 à n. Voici à quoi cela ressemble (petit rappel de tes cours de maths) : Et il y a une autre petite règle pour 0 : Si nous voulons calculer la différence entre 6! et 4! : Voyons à quoi cela ressemblerait en programmation. Nous allons explorer quelques façons de faire des calculs de factorielle en Java.

Solution ordinaire dans un programme factoriel (factorielle java)

Voici un programme factoriel simple utilisant une boucle :

class FactorialExample{
 public static void main(String args[]){
  int i,fact=1;
  int number=7;// our number to do the necessary calculations in class Factorial
  for(i=1;i<=number;i++){
      fact=fact*i;
  }
  System.out.println("Factorial of "+number+" is: "+fact);
 }
}

Notre sortie dans la console sera : Voici une autre façon de déterminer cela :

public static int getFactorial(int f) {
  int result = 1;
  for (int i = 1; i <= f; i++) {
     result = result * i; // finding factorial of number using loops
  }
  return result;
}

Rien de difficile ici : nous utilisons le nombre passé comme taille de notre boucle, dans laquelle nous multiplions par tous les nombres précédents jusqu'à ce que nous arrivions à f. Et dans main :

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

En testant le code, nous voyons que nous obtenons le résultat souhaité : 696.

Solution récursive

La récursivité se produit lorsqu'une méthode s'appelle elle-même. Une telle méthode est appelée méthode récursive. En règle générale, elle se compose de deux parties :

1. Une condition d'arrêt : lorsque la condition d'arrêt est satisfaite, la méthode doit cesser de s'appeler et commencer à faire remonter les valeurs. Après tout, s'il n'y a pas de condition d'arrêt, nous aurions une boucle infinie, la méthode s'appelant elle-même jusqu'à ce que nous nous retrouvions avec une StackOverflowError.
2. Nous devons avoir ce que la situation exige plus un appel récursif, mais avec une valeur d'entrée différente.

La fonction factorielle Java est un parfait exemple d'utilisation judicieuse de la récurrence :

public static int getFactorial(int f) { // finding factorial of number using recursive solution
  if (f <= 1) {
     return 1;
  }
  else {
     return f * getFactorial(f - 1);
  }
}

L'arrivée au nombre 1 est notre condition d'arrêt de récurrence. Si le paramètre n'a pas la valeur 1, alors nous multiplions la valeur actuelle par le résultat du prochain appel récursif à la méthode (à laquelle nous passons la valeur actuelle moins 1).

Solution avec un Stream

Si tu ne connais pas la fonctionnalité Stream de Java, ou que tu as besoin d'un petit rappel, nous t'invitons à lire ceci.

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

Ici, nous utilisons la classe spéciale IntStream, qui nous donne des fonctionnalités supplémentaires lorsque nous travaillons avec un flux de valeurs int. Pour créer un tel flux, nous utilisons sa méthode static rangeClosed, qui génère des valeurs de 2 à f (inclus) par incréments de 1. Ensuite, nous utilisons la méthode reduce pour combiner toutes les valeurs. Plus précisément, nous lui montrons comment nous voulons combiner les valeurs. Enfin, nous obtenons la valeur résultante en utilisant la méthode terminal getAsInt.

Utilisation de BigInteger

En Java, la classe BigInteger est souvent utilisée pour gérer les nombres, en particulier les GROS nombres. En effet, si nous utilisons int, la factorielle maximum que nous pouvons gérer sans perte de données est la factorielle de 31. Pour le type de données long, la factorielle maximum est de 39. Mais que faire si nous avons besoin de la factorielle de 100 ? Adaptons les solutions précédentes à BigInteger.

Solution ordinaire

public static BigInteger getFactorial(int f) { // finding factorial of number using BigInteger
  BigInteger result = BigInteger.ONE;
  for (int i = 1; i <= f; i++)
     result = result.multiply(BigInteger.valueOf(i));
  return result;
}

L'algorithme est essentiellement le même, mais ici nous utilisons les capacités de BigInteger : BigInteger.ONE est la valeur de départ 1, et multiply() sert à multiplier la valeur factorielle précédente et le nombre actuel.

Solution récursive

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

La logique générale de la solution ne change pas, la seule différence étant que certaines méthodes sont ajoutées pour travailler avec BigInteger.

Solution avec un 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();
  }
}

Tout est essentiellement pareil, mais avec l'ajout de BigInteger. La classe Stream nous donne la méthode mapToObj, que nous utilisons pour convertir les valeurs int en BigInteger afin de les multiplier entre elles en utilisant la méthode multiply (et nous avons ajouté get() pour obtenir un objet du wrapper optionnel). Si nous utilisons une de ces trois méthodes avec un argument de 100, alors nous éviterons un dépassement de la capacité de la pile et obtiendrons le bon résultat :