Exemples de Fonctions Récursives

Le calcul de la puissance d'un nombre est un exemple classique de récursivité. Vous pouvez le définir comme suit :

FONCTION puissance(base : REEL, exposant : ENTIER) : REEL
    SI exposant = 0 ALORS
        RETOURNER 1.0  // Cas de base : toute base à la puissance 0 est égale à 1
    SINON SI exposant > 0 ALORS
        RETOURNER base * puissance(base, exposant - 1)  // Cas récursif pour exposant positif
    SINON
        RETOURNER 1.0 / (base * puissance(base, -exposant - 1))  // Cas récursif pour exposant négatif
    FIN SI
FIN FONCTION
Copy

Cette fonction calcule la puissance d'un nombre en utilisant la récursivité pour traiter les exposants positifs et négatifs.

La suite de Fibonacci est une séquence numérique dans laquelle chaque nombre est la somme des deux nombres précédents. Vous pouvez la calculer de manière récursive comme suit :

FONCTION fibonacci(n : ENTIER) : ENTIER
    SI n <= 1 ALORS
        RETOURNER n  // Cas de base : les deux premiers nombres de Fibonacci sont 0 et 1
    SINON
        RETOURNER fibonacci(n - 1) + fibonacci(n - 2)  // Cas récursif
    FIN SI
FIN FONCTION
Copy

Cette fonction calcule le n-ième nombre de la suite de Fibonacci en utilisant la récursivité pour additionner les deux nombres précédents.

La recherche binaire dans un tableau trié peut également être mise en œuvre de manière récursive :

FONCTION rechercheBinaire(tableau : TABLEAU, element : ENTIER, debut : ENTIER, fin : ENTIER) : ENTIER
    SI debut > fin ALORS
        RETOURNER -1  // Cas de base : élément non trouvé
    SINON
        milieu <- (debut + fin) / 2
        SI tableau[milieu] = element ALORS
            RETOURNER milieu  // Cas de base : élément trouvé
        SINON SI tableau[milieu] > element ALORS
            RETOURNER rechercheBinaire(tableau, element, debut, milieu - 1)  // Recherche dans la moitié gauche (cas récursif)
        SINON
            RETOURNER rechercheBinaire(tableau, element, milieu + 1, fin)  // Recherche dans la moitié droite (cas récursif)
        FIN SI
    FIN SI
FIN FONCTION
Copy

La principale différence entre la récursivité et une boucle est la manière dont elles résolvent les problèmes. La récursivité divise un problème en sous-problèmes plus simples et appelle la fonction elle-même pour les résoudre. Les boucles, en revanche, répètent un ensemble d'instructions un certain nombre de fois jusqu'à ce qu'une condition de sortie soit satisfaite.

L'avantage de la récursivité est qu'elle est souvent plus expressive pour résoudre des problèmes récursifs, comme la recherche dans des structures de données complexes. Cependant, elle peut être moins efficace en termes de ressources que les boucles itératives, car chaque appel récursif ajoute une nouvelle pile d'appels. Les boucles itératives peuvent être plus efficaces dans de nombreux cas, en particulier lorsque la structure du problème permet une solution itérative directe.

En résumé, la récursivité est un outil puissant pour résoudre des problèmes qui peuvent être décomposés en sous-problèmes plus simples. Les boucles sont plus adaptées aux problèmes itératifs. Le choix entre la récursivité et les boucles dépend du problème à résoudre, de l'efficacité et de la lisibilité du code.

#cours #blindcode #algo #cours #code #blindcode

créé le 2023-10-16 à 13:41