Factorielle récursive
Fait partie de la section Logique et Flux du Journey C++ de Coddy — leçon 46 sur 56.
La factorielle d'un nombre est un exemple parfait pour démontrer la récursion en action. La factorielle de n (notée n!) est le produit de tous les entiers positifs de 1 à n. Par exemple, 5! = 5 × 4 × 3 × 2 × 1 = 120.
Ce qui rend la factorielle idéale pour la récursion, c'est qu'elle peut être définie par rapport à elle-même : n! = n × (n-1)!. Cela signifie que pour calculer 5!, vous multipliez 5 par 4!, et pour calculer 4!, vous multipliez 4 par 3!, et ainsi de suite.
Voici à quoi ressemble une fonction factorielle récursive :
int factorial(int n) {
if (n <= 1) { // Cas de base : 0! et 1! valent tous deux 1
return 1;
}
return n * factorial(n - 1); // Étape récursive : n! = n × (n-1)!
}Le cas de base arrête la récursion lorsque n atteint 1 ou 0, en renvoyant 1. L'étape récursive multiplie le nombre actuel par la factorielle du nombre immédiatement inférieur. Lorsque vous appelez factorial(4), il calcule 4 × 3 × 2 × 1 en effectuant des appels successifs jusqu'à atteindre le cas de base, puis multiplie tous les résultats ensemble au fur et à mesure que les appels aboutissent.
Défi
FacileCréez un programme qui implémente une fonction factorielle récursive et l'utilise pour calculer les factorielles de différentes valeurs d'entrée. Ce défi testera votre compréhension du fonctionnement de la récursion en demandant à une fonction de s'appeler elle-même avec des paramètres modifiés jusqu'à ce qu'elle atteigne un cas de base.
L'entrée suivante sera fournie :
- Un entier
nreprésentant le nombre pour lequel calculer la factorielle
Votre programme doit :
- Créer une fonction récursive nommée
factorialqui prend un paramètre entier et retourne un entier - La fonction doit implémenter le cas de base : si
nest inférieur ou égal à 1, retourner 1 - La fonction doit implémenter l'étape récursive : retourner
nmultiplié par la factorielle den-1 - Dans la fonction principale, lire la valeur d'entrée
- Appeler la fonction factorielle avec la valeur d'entrée
- Afficher le résultat en utilisant le format spécifié
Utilisez exactement le format de sortie suivant :
Factorial of [n] is [result]N'oubliez pas que la fonction factorielle doit s'appeler elle-même avec une valeur plus petite à chaque fois, se rapprochant du cas de base à chaque appel récursif. Le cas de base empêche la récursion infinie en s'arrêtant lorsque n atteint 1 ou 0. L'étape récursive multiplie le nombre actuel par la factorielle du nombre immédiatement inférieur, construisant le résultat final au fur et à mesure que les appels de fonction retournent leurs valeurs.
Aide-mémoire
La factorielle de n (n!) est le produit de tous les entiers positifs de 1 à n. Elle peut être définie de manière récursive comme suit : n! = n × (n-1)!
Fonction factorielle récursive :
int factorial(int n) {
if (n <= 1) { // Cas de base : 0! et 1! valent tous deux 1
return 1;
}
return n * factorial(n - 1); // Étape récursive : n! = n × (n-1)!
}Le cas de base arrête la récursion lorsque n atteint 1 ou 0. L'étape récursive multiplie le nombre actuel par la factorielle du nombre immédiatement inférieur.
Essayez vous-même
#include <iostream>
using namespace std;
// TODO: Écrivez votre fonction factorielle ici
int main() {
// Lire l'entrée
int n;
cin >> n;
// TODO: Appeler la fonction factorielle et stocker le résultat
// Afficher le résultat
cout << "Factorial of " << n << " is " << result << endl;
return 0;
}
Testez-vousCette leçon comprend un petit quiz. Commencez la leçon pour y répondre et suivre votre progression.
Toutes les leçons de Logique et Flux
1Pointeurs et mémoire
Qu'est-ce qu'un pointeur ?Opérateur d'adresseOpérateur de déréférencementPointeurs nulsPointeurs et tableauxMémoire dynamique avec 'new'Libérer la mémoire avec 'delete'Récapitulatif - Pratique des pointeurs4Maps (Paires Clé-Valeur)
Introduction à std::mapCréer une MapAccéder aux valeurs et les modifierVérifier l'existence de clésSupprimer des pairesParcourir une MapRécapitulatif - Fréquence des mots7Fonctions avancées
Passage par référenceIntroduction aux expressions LambdaLambdas avec paramètresLambdas avec valeurs de retourIntroduction à la récursivitéFactorielle récursiveTri par Lambda2Vecteurs (Tableaux dynamiques)
Introduction à std::vectorCréer un vecteurAjouter des élémentsAccéder aux élémentsTaille d'un vecteurItérer avec une boucle ForBoucle For basée sur l'intervalleSupprimer des élémentsRécapitulatif - Opérations sur les vecteurs3Projet : Outil de liste de tâches
Présentation du projetAjouter une tâche
Afficher les tâchesSupprimer une tâcheFinaliser l'outil