Dans cette leçon d'algorithmique, le présentateur introduit la notion de récursivité comme une forme d'itération où une fonction s'appelle elle‑même. Après avoir rappelé les trois boucles classiques (tant que, pour, répéter) et montré comment elles permettent de calculer la somme des dix premiers entiers, il expose un premier algorithme récursif incomplet qui, faute de condition d'arrêt, conduit à une boucle infinie. Il montre alors comment ajouter une condition de base (nbr = 0) pour garantir la terminaison et obtenir la somme correcte. Le même principe est appliqué à la fonction factorielle. Le cours souligne les avantages de la récursivité – code plus court, plus lisible, parfois plus rapide (ex. tris, animations en JavaScript/ActionScript) – et précise que certains langages l’utilisent couramment. Enfin, il implémente en Python les deux fonctions récursives (somme et factorielle), présente le code, les appels d’exemple (somme(10)=55, fact(3)=6, fact(5)=120) et conclut en invitant les apprenants à pratiquer.
Chapters
Bonjour à tous et bienvenue dans cette nouvelle leçon d'algorithmique. Aujourd'hui nous allons traiter la récursivité. Dans la leçon où nous avons traité les fonctions et procédures, j'ai évoqué le terme récursivité ou fonction récursive. La récursivité est une sorte d'itération qui donne lieu à un traitement répétitif comme celui assuré par les 3 boucles classiques, à savoir: tant que, pour et répéter. Cependant, ce traitement itératif est assuré par une fonction dite fonction récursive. Une fonction récursive est une fonction qui s'appelle elle-même, autrement dit, dans le corps même de la fonction on trouve l'appel de celle-ci. Donc à chaque fois qu'elle s'exécute, elle s'appelle, ce qui l'amène à se réexécuter de manière séquentielle. Bien entendu, une récursivité mal exprimée mène à un traitement infini, exactement comme une structure itérative mal formulée qui mène à une boucle infinie. Imaginons que l'on souhaite écrire un algorithme qui calcule la somme des 10 premiers entiers positifs. On peut faire ce traitement avec les boucles comme ceci. À l'aide de la boucle TantQue, on aura l'algorithme suivant: Avant d'entrer dans la structure itérative, on initialise le compteur de la boucle représenté par la variable i à 1 et la somme S à 0. Dans la boucle, on affecte à S son ancienne valeur à laquelle on a ajouté la valeur actuelle du compteur. Puis on incrémente celui-ci de 1. Autrement dit, avant d'entrer dans la boucle, S vaut 0. Une fois dans celle-ci, S vaut 1 lors de la première itération, puis 3 dans la deuxième itération, etc. À l'aide de la boucle Pour, on aura ceci: Et à l'aide de la boucle Répéter, on aura cet algorithme: Donc vous avez vu que dans les 3 boucles nous avons répété le même traitement 10 fois, tout en incrémentant la variable i de 1 à chaque itération. Bien entendu, la condition de sortie de la boucle Répéter est légèrement différente vu sa particularité. Maintenant, essayons de faire la même chose mais cette fois en recourant à la récursivité à l'aide d'une fonction récursive. Je propose cet algorithme: Vous avez peut-être remarqué l'absence du bloc consacré à la déclaration des variables dans l'algorithme principal et aussi dans la fonction. En effet, dans cet algorithme nous n'aurons besoin d'aucune variable à part la variable locale nbr qui constitue l'argument de la fonction, et qui sera initialisée statiquement au moment de l'appel avec la valeur 10. Examinons maintenant ce qui va se passer. Dans le corps de l'algorithme, on appelle la fonction nommée FoncRec qui insinue fonction récursive. Sa valeur de retour sera affichée à l'aide de la fonction à écrire. Au moment de l'appel de la fonction, on passe la valeur 10 en guise d'argument. Cette valeur sera assignée à la valeur locale nbr. Dans le corps de la fonction, on remplace nbr par sa valeur ce qui donne le résultat 10+ FoncRec. Cette expression constitue la valeur de retour de la fonction, ce qui signifie que l'on doit sortir de celle-ci en retournant ce résultat-là. Cependant, ce dernier dépend encore de l'exécution de la fonction Fonc_grecque elle-même, en lui passant cette fois la valeur 9. Alors, vous êtes conscient que Fonc_grecque est une fonction récursive dont le résultat de retour dépend de sa réexécution. Autrement dit, la fonction Ecrire déclarée dans le corps de l'algorithme principal est mise en instance jusqu'à ce que Fonc_grecque finisse son traitement afin qu'elle retourne son résultat au complet. À la fin, FoncGrecq est censée retourner 10+ 9+ 8+ 7 etc. Or, rien n'indique à la fonction quand est-ce qu'elle doit arrêter sa récursivité. En effet, au bout d'un certain moment nbr vaudra 0, puis -1, puis -2 et ça continuera ainsi à l'infini. Nous sommes donc tombés dans une sorte de boucle infinie. Pour pallier ce problème, on doit intercaler une condition qui indiquera à la fonction quand est-ce qu'elle doit se réexécuter et quand est-ce qu'elle doit mettre fin et retourner le résultat final une fois pour toutes. Nous allons donc améliorer notre algorithme comme ceci: Dans ce cas, tant que la variable nbr est supérieure à 0, on appelle la fonction FoncGrecque par récursivité. Mais une fois nbr passe à 0, on retourne 0 qui est un élément neutre de l'addition. La valeur de retour finale de la fonction vaut donc 10+ 9+ 8 jusqu'à+ 0, et c'est ce résultat que l'on affichera à l'aide de la fonction Ecrire dans l'algorithme principal. De la même manière, la fonction qui permet de calculer la factorielle d'un entier par récursivité, et que l'on a déjà vue dans la leçon où j'ai traité les fonctions et procédures est la suivante. À la fin, sachez que la récursivité s'avère quelquefois utile, comme dans les algorithmes de tri par exemple. En effet, l'exécution prend moins de temps dans ce genre de problèmes que si l'on y procède via les boucles classiques. Une fonction récursive est aussi souvent plus courte à écrire, donc plus lisible. Notez que certains langages de programmation comme JavaScript ou ActionScript utilisent souvent des fonctions récursives pour réaliser les animations. Maintenant, nous allons implémenter notre algorithme qui calcule la somme des n premiers nombres entiers positifs avec une fonction récursive à l'aide du langage Python. On commence par déclarer la fonction, on lui passe en argument nbr, on met la condition, donc si nbr est supérieur à 0, on retourne le résultat suivant, c'est-à-dire nbr+ FoncRec . Donc vous avez remarqué l'appel récursif de la fonction FoncRec. Sinon, on retourne 0. On sort maintenant de la fonction, puis on va afficher ceci: C'est-à-dire la somme des 10 premiers entiers positifs en exécutant la fonction FoncY. Exécutons. Ça donne 55. Si je change de valeur, par exemple 3, on est censé avoir 1+ 2+ 3, ce qui donne 6. Et voilà. On fait la même chose pour la factorielle. Donc si nbr est égal à 0, on retourne 1. Sinon, dans ce cas on retourne nbr multiplié par fact . C'est encore un appel récursif de la fonction fact. Maintenant on affiche la factorielle d'un nombre, par exemple 3, on est censé avoir 6. Voilà. La factorielle de 5 c'est 120, etc. Alors j'espère que vous avez compris comment appréhender les fonctions récursives. Merci pour votre attention et à la vidéo prochaine.
