Qu’est-ce que la récursivité ?
En matière de programmation, on peut répondre brièvement qu’il y a récursivité lorsqu’une méthode s’appelle elle-même. Une autre forme de récursivité, un peu plus complexe, et moins « visible » est la récursivité circulaire qui se produit lorsqu’une méthode « A » appelle une méthode « B » qui elle même appelle la méthode « A ». Le nombre de méthode n’est d’ailleurs pas forcément limité à deux… : A->B->C…->A est aussi un cas de programmation récursive, mais qui hélas est parfois involontaire, et dans ce cas, souvent difficile à détecter. De toutes les façons, ce troisième cas est à proscrire pour des raisons évidentes de difficulté à suivre le code, à le débuguer et à le maintenir.
Un cas d’école: La factorielle
L’exemple le plus simple est celui de la fonction « factorielle » qui peut être écrite de façon récursive et ce, même si dans ce cas précis, ce n’est ni la façon la plus rapide ni la plus efficace.
Afin de se rafraîchir la mémoire rappelons que la factorielle(n) – qui se note n! -est égal à 1*2*3*4*…*n ou bien encore n*(n-1)*(n-2)*(n-3)… *1.De plus factorielle(0) = 1 Partant de là, on peut dire que n! = n * (n-1)! Puis, n*(n-1)*(n-2)!, etc, jusqu’à ce que (n-x) soit égal à 0.
L’exemple le plus simple est celui de la fonction « factorielle » qui peut être écrite de façon récursive et ce, même si dans ce cas précis, ce n’est ni la façon la plus rapide ni la plus efficace.
Afin de se rafraîchir la mémoire rappelons que la factorielle(n) – qui se note n! -est égal à 1*2*3*4*…*n ou bien encore n*(n-1)*(n-2)*(n-3)… *1.De plus factorielle(0) = 1 Partant de là, on peut dire que n! = n * (n-1)! Puis, n*(n-1)*(n-2)!, etc, jusqu’à ce que (n-x) soit égal à 0.
Quand une méthode, appelle une autre méthode…
Ce principe est immuable et doit être respecté également pour une méthode récursive.
Une méthode « A » qui appelle une méthode « A » doit récupérer la main, de même qu’une méthode « A » appelée par une méthode « A » doit rendre la main. À chaque appel le « niveau » de recursivité augmente, à chaque retour le niveau diminue.
les contourner ou de les éviter, mais offrent des exemples de solutions à des problèmes qui, sans la possibilité de programmation récursive seraient certainement plus ardus à résoudre.
Exemple 1 : Recherche de fichiers sur disques
Il est évident que pour chercher un fichier sur un disque, il faut ouvrir un volume et regarder son contenu, qui comme chacun sait, est constitué de dossiers et de fichiers. Nous en obtiendrons la liste grâce aux commandes..
LISTE DES DOCUMENTS et LISTE DES DOSSIERS.
Une fois ces listes constituées, nous devrons :
1°) chercher la chaîne souhaitée dans chacun des éléments,
2°) à partir de la nouvelle liste de dossiers effectuer, dossier par dossier, une nouvelle recherche.
Le « niveau» de la recherche récursive dépendra du nombre de dossiers imbriqués les uns dans les autres. Dans le cas d’un disque dur, ce nombre est vraisemblablement raisonnable car il ne s’agit pas de la quantité totale de dossiers d’un disque dur, mais de la profondeur maximum de leurs imbrications.
Ce principe est immuable et doit être respecté également pour une méthode récursive.
Une méthode « A » qui appelle une méthode « A » doit récupérer la main, de même qu’une méthode « A » appelée par une méthode « A » doit rendre la main. À chaque appel le « niveau » de recursivité augmente, à chaque retour le niveau diminue.
les contourner ou de les éviter, mais offrent des exemples de solutions à des problèmes qui, sans la possibilité de programmation récursive seraient certainement plus ardus à résoudre.
Exemple 1 : Recherche de fichiers sur disques
Il est évident que pour chercher un fichier sur un disque, il faut ouvrir un volume et regarder son contenu, qui comme chacun sait, est constitué de dossiers et de fichiers. Nous en obtiendrons la liste grâce aux commandes..
LISTE DES DOCUMENTS et LISTE DES DOSSIERS.
Une fois ces listes constituées, nous devrons :
1°) chercher la chaîne souhaitée dans chacun des éléments,
2°) à partir de la nouvelle liste de dossiers effectuer, dossier par dossier, une nouvelle recherche.
Le « niveau» de la recherche récursive dépendra du nombre de dossiers imbriqués les uns dans les autres. Dans le cas d’un disque dur, ce nombre est vraisemblablement raisonnable car il ne s’agit pas de la quantité totale de dossiers d’un disque dur, mais de la profondeur maximum de leurs imbrications.
(Ex : MonVolume/MesDocuments/MesImages/MesDessins/MaMaison/MaCuisine…)
Exemple2 : Comment faire des anagrammes ?
Rappelons qu’une anagramme est une combinaison de lettres effectuée à partir d’une série de lettres quelconques.
Par exemple, NICHE est l’anagramme de CHIEN, de même que « ABCD » est l’anagramme de « BADC » Dans un premier temps, afin de programmer le plus simplement possible et de nous écarter le moins possible du sujet nous ignorerons les lettres doubles.
Les exceptions seront traitées dans un second exemple optimisé, inspiré du premier.
Exemple 3 : Une méthode devient un process !
Ce troisième exemple est un peu particulier, et ce, à deux points de vue.
1°) Il s’agit d’utiliser la même méthode pour créer un process et pour l’exécuter.
2°) C’est une méthode « pseudo » récursive..
Exemple2 : Comment faire des anagrammes ?
Rappelons qu’une anagramme est une combinaison de lettres effectuée à partir d’une série de lettres quelconques.
Par exemple, NICHE est l’anagramme de CHIEN, de même que « ABCD » est l’anagramme de « BADC » Dans un premier temps, afin de programmer le plus simplement possible et de nous écarter le moins possible du sujet nous ignorerons les lettres doubles.
Les exceptions seront traitées dans un second exemple optimisé, inspiré du premier.
Exemple 3 : Une méthode devient un process !
Ce troisième exemple est un peu particulier, et ce, à deux points de vue.
1°) Il s’agit d’utiliser la même méthode pour créer un process et pour l’exécuter.
2°) C’est une méthode « pseudo » récursive..
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours 4D (Récursivité) (331 KO) (Cours PDF)
