La factorielle d'un nombre est un concept mathématique important. Vous pouvez l'utiliser pour effectuer des permutations et des combinaisons, écrire des expressions exponentielles et logarithmiques et calculer des probabilités.
Vous l'utilisez pour trouver le nombre de façons différentes de concevoir une disposition des sièges ou de choisir des t-shirts pour vos vacances aux Maldives. Mais comment calculer la factorielle d'un nombre ?
Qu'est-ce que la factorielle d'un nombre ?
La factorielle d'un nombre positif est le produit de tous les entiers positifs inférieurs ou égaux à la valeur du nombre lui-même. Un nombre suivi d'un point d'exclamation (!) indique la factorielle d'un nombre. Vous représentez la factorielle de cinq par 5! et calculez-le comme suit :
5! = 5 * 4 * 3 * 2 * 1 = 120
Une autre façon de le visualiser est :
5! = 5 * 4! où 4! = 4 * 3!, 3! = 3 * 2! et ainsi de suite jusqu'à ce que vous obteniez 1! = 1 * 0! qui vaut 1.
Vous utiliserez ce concept pour construire notre programme factoriel en utilisant un concept populaire appelé récursivité.
Qu'est-ce que la récursivité ?
La récursivité est un processus dans lequel une fonction s'appelle elle-même. L'un des principaux avantages de ce processus est qu'il décompose un problème plus important en plus petits morceaux. Cela rend le problème plus facile à résoudre.
Vous pouvez utiliser la récursivité pour résoudre des problèmes appropriés en trois étapes simples :
- Trouvez le cas de base : Si une fonction s'appelle toujours elle-même, le processus sera infini. Pour éviter que cela ne se produise, définissez un cas de base qui devient le point d'arrêt logique de votre fonction. Par exemple, dans un programme factoriel, arrêtez le calcul à zéro. Cela devient le cas de base du problème.
- Trouvez la relation entre le problème et les sous-problèmes: Décomposez le plus gros problème en un sous-problème. Par exemple, le problème est de trouver la factorielle de cinq. Supposons que vous ayez la réponse du factoriel de quatre, c'est-à-dire 24. Comment obtiendrez-vous la factorielle de cinq en utilisant 24? En multipliant cinq lui-même en lui. C'est la relation entre le problème et le sous-problème.
- Généralisez la relation trouvée à l'étape 2: Maintenant que vous avez la relation, généralisez-la en termes de n. Ainsi, la factorielle d'un nombre n est le produit de n et la factorielle de n-1.
Vous pouvez utiliser ce concept pour trouver la somme de n nombres naturels, calculer GCD, LCM, la série de Fibonacci et vérifier les nombres premiers.
Pseudo-code pour la fonction factorielle utilisant la récursivité
C'est comment vous utilisez la récursivité et écrivez le pseudo-code pour construire votre programme dans n'importe quel langage. Avec différents langages, la syntaxe et l'exécution changent mais la logique reste intacte.
fonctionFait(n)
Si n == 0 alors // cas de base
Retour1
Retour n * Fait d'appel (n - 1) // relation généralisée
Programme factoriel en C
C était le premier langage de programmation de haut niveau indépendant de la plate-forme. Il a une syntaxe stricte, est sensible à la casse et exécute le code avec la vitesse la plus rapide. C'est un langage de programmation procédural et donc vous déclarez n'importe quelle fonction au-dessus du principal fonction. Voici comment vous pouvez construire le programme factoriel en utilisant la récursivité en langage C :
Vous pouvez trouver le code source complet du programme factoriel utilisant la récursivité en C, Java et Python dans ce Référentiel GitHub.
- Importez le fichier d'en-tête de sortie d'entrée standard pour afficher la sortie à l'écran.
#inclure <stdio.h> - Définir la fonction fait et prendre un entier n comme argument.
entierfait(entier n){ - Écrivez le cas de base de la fonction à l'aide de la si déclaration et vérifier son égalité en utilisant ==. Si n est égal à zéro, renvoie un.
si (n == 0)
retour1; - Écrire l'équation généralisée et retourner le produit de n avec un appel de fonction de sous-problème n-1.
retour n * fait (n - 1);
} - Déclarez la fonction main et initialisez une variable de type entier pour stocker le nombre dont vous voulez trouver la factorielle.
entierprincipal(){
entier nombre = 5; - Affichez la factorielle du nombre à l'aide de la printf() fonction. %d est le spécificateur de format décimal. Utilisez chacun des spécificateurs de format pour le remplacer par le nombre dont vous souhaitez trouver la factorielle et obtenez le résultat en appelant la fonction.
printf("Le factoriel de %d est %d", num, fait (num));
retour0;
}
Programme factoriel en Java
Java est un langage de programmation compilé et indépendant de la plate-forme. Vous stockez tout le code dans un classe et l'exécution commence à partir du principal fonction. Il est sensible à la casse et à la syntaxe stricte. Le code est un peu plus long mais plus rapide par rapport à Python. Voici comment vous pouvez construire le programme factoriel en utilisant la récursivité en Java :
- Définissez la classe principale.
classePrincipal{ - Définissez une fonction statique avec le type de retour int qui accepte une variable n de type entier. Vous avez déclaré une méthode statique car la méthode principale en Java est également déclarée comme statique. De plus, vous ne pouvez pas appeler une méthode non statique à partir d'une instance statique.
statiqueentierfait(entier n){ - Écrivez le cas de base de la fonction à l'aide de la si déclaration et vérifier son égalité en utilisant ==. Si n est égal à zéro, renvoie un.
si (n == 0)
retour1; - Écrire l'équation généralisée et retourner le produit de n avec un appel de fonction de sous-problème n-1.
retour n * fait (n - 1);
} - Déclarez la fonction principale en Java. Déclarez le modificateur d'accès comme public, il peut donc être accessible par toutes les autres classes et méthodes. Vous déclarez la fonction principale comme statique afin que le compilateur puisse l'invoquer sans instancier la classe. Le type de retour est annuler, et il accepte des arguments de type Chaîne. Enregistrez le nombre dont vous voulez trouver la factorielle.
publicstatiqueannulerprincipal(Chaîne [] arguments){
entier nombre = 5; - Utilisez le println() méthode, une instance de la PrintStream classe, définie dans la Système classe pour afficher la factorielle du nombre.
System.out.println("Factoriel de " + nombre + " est " + fait (num));
}
}
Programme factoriel en Python
Écrire du code en Python est super facile et amusant. Comme il s'agit d'un langage interprété indépendant de la plate-forme, vous n'avez pas à déclarer le type de données des variables. Vous évitez également d'avoir à déclarer des classes et à importer des bibliothèques pour un programme aussi simple. Le terrain de jeu est prêt pour que vous commenciez à coder.
La syntaxe est plus simple, avec une petite longueur de code mais prend un peu plus de temps à s'exécuter que les autres langages. Voici comment vous pouvez construire le programme factoriel en utilisant la récursivité en Python :
- Définir la fonction fact qui accepte comme argument n.
définitivementfait(n): - Écrivez le cas de base de la fonction à l'aide de la si déclaration et vérifier son égalité en utilisant ==. Si n est égal à zéro, renvoie un.
si n == 0 :
retour1 - Écrire l'équation généralisée et retourner le produit de n avec un appel de fonction de sous-problème n-1.
retour n * fait (n-1) - Enregistrez le nombre dont vous voulez trouver la factorielle et affichez-le à l'aide de l'instruction d'impression.
nombre = 5 ;
imprimer("Factoriel de", nombre, "est", fait (num))
Il existe de nombreuses applications de la récursivité
La récursivité est un moyen efficace de résoudre des problèmes. C'est le nœud de l'intelligence artificielle et il a des utilisations dans le monde réel dans des jeux de réflexion tels que les échecs ou le sudoku.
C'est également une méthode puissante pour trier des structures de données telles que Tree ou des algorithmes de tri tels que Quick sort et Merge sort. Vous pouvez également utiliser la récursivité dans des algorithmes de recherche tels que la recherche binaire, des expressions mathématiques telles que la série de Fibonacci, etc.