RÉCURSIVITÉ: PLACER HUIT REINES SUR UN ÉCHIQUIER
BruNews
Messages postés
21040
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
20 févr. 2008 à 19:36
neamar Messages postés 26 Date d'inscription vendredi 9 septembre 2005 Statut Membre Dernière intervention 12 avril 2009 - 16 mars 2008 à 13:29
neamar Messages postés 26 Date d'inscription vendredi 9 septembre 2005 Statut Membre Dernière intervention 12 avril 2009 - 16 mars 2008 à 13:29
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/45801-recursivite-placer-huit-reines-sur-un-echiquier
https://codes-sources.commentcamarche.net/source/45801-recursivite-placer-huit-reines-sur-un-echiquier
16 mars 2008 à 13:29
La récursivité est certes plus longue que la méthode itérative...et encore, seulement si on utilise des procédures qui ne sont pas tail-rec (récursion terminale, voir plus bas..mais bon, c'est seulement pour la curiosité : VB ne gère pas le tail rec...)
Je me permets cependant de citer un excellent tutorial sur la récursivité :
"
D'une part, le tail-rec se justifie pour des questions de performances. Mais il faut savoir que les performances ne sont pas le seul but que doit viser le programmeur. Dans certain cas, elles ne sont même pas vraiment importantes (par exemple, quand on interagit avec l'utilisateur, qui est mille fois plus lent à choisir un bouton à la souris que n'importe quelle factorielle récursive codée avec les pieds), d'ailleurs il suffit de voir le nombre de gens qui codent dans des langages "lents", comme PHP, Python ou Ruby par exemple.
Bref, un autre aspect à ne pas négliger du code est la lisibilité. Là, l'utilisation de fonctions tail-rec devient plus controversée. Il y a deux cas : soit la fonction est naturellement tail-récursive (un compte à rebours par exemple) et ça ne pose aucun problème, soit la fonction demande une transformation, et alors vous devez peser le pour et le contre avec soin : la transformation pose-t-elle des problèmes de lisibilité ? Si vous n'utilisez qu'une seule fois la fonction dans votre programme, privilégiez plutôt la lisibilité, et laissez la "non tail-rec". Si elle est souvent utilisée et constitue une part non négligeable du temps utilisé par votre programme (il existe des outils pour mesurer ça), choisissez la version tail-rec. De toute façon, de nombreux programmeurs sont habitués à reconnaître le motif "accumulateur de fonction tail-rec" (choisissez un nom clair pour l'argument accumulateur supplémentaire), et cela ne leur posera donc aucun problème.
D'autre part, certaines fonctions ne peuvent pas devenir tail-récursives. Comme nous l'avons vu, une fonction est tail-récursive quand l'appel récursif est la dernière chose effectuée par la fonction. Qu'en est-il des fonctions qui font plusieurs appels récursifs (notre exemple max_pommes par exemple) ? Et bien c'est simple, ces fonctions ne peuvent tout simplement pas être rendues tail-récursives : seul le dernier appel pourrait être converti en appel terminal, et tous les autres appels (dans la boucle for de notre exemple) augmenteront la pile d'appels.
Cela pose-t-il un problème fondamental ? La réponse est non. En effet, la justification de l'optimisation tail-rec des fonctions est d'obtenir les mêmes performances que la version itérative. Pour ce genre de fonctions (récursivité à appels multiples), il n'existe pas de version itérative équivalente qui soit aussi simple. La version récursive est donc la seule manière simple de formuler le problème, et toutes les versions itératives basées sur cet algorithme devront trouver une manière de remplacer la pile d'appels (qui stocke des informations qui nous arrangent), et leurs performances ne seront donc pas meilleures.
"
(source : http://www.siteduzero.com/tuto-3-23774-1-la-recursivite.html )
Et pour conclure, je souligne la dernière phrase de la citation : certes, la récursivité est plus lente que l'itératif...MAIS si on utilise la méthode récursive, c'est souvent parce que la méthode itérative est inapplicable ou encore beaucoup plus lourde. Par exemple, dans cette source (http://www.vbfrance.com/codes/VRAIE-CALCULATRICE-ECRITURE-2D-ON-MARQUE-LIGNE-ENTIERE_46070.aspx ), l'utilisation de la récursivité pour le calcul est obligatoire : programmer avec un mode itératif serait 100 fois plus complexe et moins lisible.
26 févr. 2008 à 11:01
Cela dit, je reconnais qu'un programme est souvent plus simple à faire en récursif, et il est parfois très difficile de l'adapter en récursif.(ayant moi même aussi programmé les programmes dont tu parles dans la description (tours de hanoi, trajet du cavalier pour se déplacer sur toutes les cases (et suivant la configuration, se retrouver sur son point de départ à la fin ou non), et le placement des dames sur l'échiquier), ainsi que pas mal de programmes de jeu avec intelligence artificielle.
23 févr. 2008 à 09:21
Dans la fonction « PlacerReine », on peut remplacer « bRetour = True » par Stop pour obtenir les différentes combinaisons possibles avec leur variantes.
Les variantes sont les mêmes combinaisons obtenues en tournant l’échiquier d’un quart ou d’un demi-tour.
Dans cet exemple, l’inconvénient de la programmation récursive est qu’il est très difficile (voir impossible) de modifier le programme de façon à obtenir uniquement les différentes combinaisons sans les variantes.
20 févr. 2008 à 22:52
Merci de votre commentaire, mais permettez-moi de le tempérer un peu.
Certes, rien n'est parfait en ce bas monde, mais je ne suis pas d'accord pour dire que la récursivité n'est qu'un pis aller en attendant mieux.
C'est vrai, le risque de débordement de pile est tout à fait réel, j'ai pu en rencontrer au temps où j'utilisais le C7.0. En effet, mettre en oeuvre la récursivité demande quelques précautions: comprendre le "mécanisme logiciel" mis en jeu, estimer le niveau maximum de réentrance, minimiser les paramètres passés ainsi que les variables locales. Pour autant, ce n'est pas une méthode à délaisser.
Pour ce qui est des performances, cela ne peut se juger qu'au cas par cas. Par ailleurs, aux performances du programme, il faut aussi confronter le coût de développement.
Le tournevis et le marteau sont deux très bons outils, mais suivant mes besoins, j'utiliserai l'un, l'autre, ou les deux, à moins que ce ne soit un troisième.
20 févr. 2008 à 19:36
- Risque d'explosion de la stack.
- Perte de perfs due à l'empilage et dépilage des params.
Voilà qui rend la récursivité nettement moins élégante.
Pour résumer, en prod une fonction ne reste en version récursive que tant qu'on a pas réussi à la rendre itérative.