Récursivité
Glissez pour afficher le menu
Récursivité en programmation désigne la technique où une fonction s'appelle elle-même pour résoudre une version plus petite du même problème. Il s'agit d'une méthode puissante et élégante pour résoudre des problèmes pouvant être décomposés en sous-problèmes du même type.
Les fonctions récursives comportent généralement deux composants :
-
Cas de base : Définit la condition d'arrêt pour la fonction récursive. Lorsque le cas de base est atteint, la fonction cesse de s'appeler et retourne une valeur spécifique. Ceci est nécessaire pour éviter une récursivité infinie.
-
Cas récursif : Définit la logique permettant de décomposer le problème en sous-problèmes plus petits et d'appeler la fonction de manière récursive avec des entrées réduites. Le cas récursif permet à la fonction de progresser vers le cas de base.
La factorielle d'un nombre n est définie comme suit :
n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!
main.cpp
12345678910111213141516171819#include <iostream> // Function to calculate factorial int factorial(int n) { // Base case: factorial of 0 or 1 is 1 if (n == 0 || n == 1) return 1; // Recursive case: multiply n with factorial of (n-1) std::cout << "Recursive Case: " << n << " * factorial(" << n - 1 << ")" << std::endl; return n * factorial(n - 1); } int main() { // Call the function std::cout << factorial(5) << std::endl; }
Cas de base : Le cas de base correspond à l'entrée n égale à 0 ou 1. Dans ce cas, la factorielle est définie comme 1. Le cas de base garantit que la récursivité se termine et empêche une récursion infinie.
Cas récursif : Le cas récursif correspond à la logique de calcul de la factorielle de n lorsque n est supérieur à 1. Il s'agit d'appeler la fonction factorielle de manière récursive avec n - 1 comme argument et de multiplier le résultat par n. Cela réduit le problème à un sous-problème plus petit en calculant la factorielle d'un nombre inférieur.
Appel de la fonction avec l'argument égal à 5. Voici le processus étape par étape :
factorial(5)appellefactorial(4)et multiplie le résultat par 5.factorial(4)appellefactorial(3)et multiplie le résultat par 4.factorial(3)appellefactorial(2)et multiplie le résultat par 3.factorial(2)appellefactorial(1)et multiplie le résultat par 2.factorial(1)est le cas de base et retourne 1.- la multiplication continue en remontant la chaîne, ce qui donne la factorielle finale de
5qui est égale à120.
Merci pour vos commentaires !
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
