Récursion

La récursivité en programmation fait référence à la technique où une fonction s'appelle elle-même pour résoudre une instance plus petite du même problème. C'est une manière puissante et élégante de résoudre des problèmes pouvant être divisés en sous-problèmes plus petits du même type.

Les fonctions récursives se composent généralement de deux composantes :

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écursion infinie.
Cas récursif : Il définit la logique de décomposition du problème en sous-problèmes plus petits et l'appel récursif de la fonction avec des entrées réduites. Le cas récursif permet à la fonction de progresser vers le cas de base.

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

Remarque

Le factoriel d'un nombre n est défini comme suit:
n! = n*(n-1)*(n-2)*..*2*1 = n*(n-1)!

main


              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 1. Ce cas de base garantit que la récursion se termine et empêche une récursion infinie.

Cas récursif: Le cas récursif consiste en la logique nécessaire pour calculer la factorielle de n lorsque n est supérieur à 1. Il s'agit d'appeler la fonction 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 en calculant la factorielle d'un nombre inférieur.

Appel de la fonction avec un 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 renvoie 1.
La multiplication se poursuit en remontant la chaîne, donnant la factorielle finale de 5 qui équivaut à 120.

Tout était clair ?

Merci pour vos commentaires !

Section 4. Chapitre 3