Apprendre Récursivité | Quelques Sujets Avancés

La 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 : Il 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 : Il définit la logique permettant de décomposer le problème en sous-problèmes plus petits et d'appeler la fonction récursivement avec des entrées réduites. Le cas récursif permet à la fonction de progresser vers le cas de base.

Essayons de calculer la factorielle d'un nombre en utilisant la récursivité.

Remarque

La factorielle d'un nombre n est définie comme suit :
n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!

main.cpp


              1234567891011121314151617181920
            
#include <iostream>

// Function to calculate factorial
int factorial(int n) {
    // Base case: factorial of 0 or 1 is 1
    if (n == 0 || n == 1) {
        std::cout << "Base Case: return 1" << std::endl;
        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;
}

Fournissons une explication étape par étape du code ci-dessus :

Cas de base : Le cas de base se produit lorsque l'entrée n est égale à 0 ou 1. Dans ce cas, la factorielle est définie comme étant 1. Le cas de base garantit que la récursivité s'arrête et empêche une récursivité infinie.

Cas récursif : Le cas récursif correspond à la logique de calcul de la factorielle de n lorsque n est supérieur à 1. Cela consiste à appeler récursivement la fonction factorielle avec n - 1 comme argument et à 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) appelle factorial(4) et multiplie le résultat par 5.
factorial(4) appelle factorial(3) et multiplie le résultat par 4.
factorial(3) appelle factorial(2) et multiplie le résultat par 3.
factorial(2) appelle factorial(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 5 qui est égale à 120.

Tout était clair ?

Merci pour vos commentaires !

Section 4. Chapitre 3

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Suggested prompts:

Can you show me the code for the recursive factorial function?

Can you explain how recursion works with another example?

What happens if there is no base case in a recursive function?

Awesome!

Completion rate improved to 5

Glissez pour afficher le menu