Récursivité: placer huit reines sur un échiquier

Soyez le premier à donner votre avis sur cette source.

Vue 11 418 fois - Téléchargée 331 fois

Description

Cet exemple illustre la programmation récursive.
La méthode récursive est une méthode "bourrin", - c'est vrai, - puisqu'elle va explorer toutes les possibilités jusqu'à trouver une solution, mais c'est parfois la seule méthode qui tienne la route, (rien n'empêche d'optimiser la recherche si c'est possible).
Mais sa principale qualité est qu'elle permet une programmation élégante, je dirais même limpide. Pour autant, les premières fois que l'on tente de la mettre en oeuvre, on peut se faire des noeuds à la tête !
Elle s'applique lorsque l'on est confronté à un problème que l'on ne sait pas résoudre, mais que l'on peut décomposer en problèmes élémentaires de même nature.
La solution du problème de complexité C est alors une fonction simple de la solution du problème de complexité C-1.

L'exemple bateau est le calcul de la fonction factorielle: Factorielle(e) = e x (e-1) x e(-2) x ... x 3 x 2 x 1,
(e étant un entier positif; si e est nul, Factorielle(e)=1).
Première solution: faire une boucle, (dans ce cas c'est la meilleure méthode).
Deuxième solution: l'algorithme récursif qui peut se programmer ainsi:
Private Function Factorielle(ByVal e As Long) As Long
If e <= 1 Then
Factorielle = 1
Else
Factorielle = e * Factorielle(e - 1)
End If
End Function
Remarques: e est supposé positif et pas trop grand pour éviter les overflow.
Il faudrait ajouter les contrôles d'erreur.

Quelques exemples de problèmes pouvant être résolus par récursivité:
- les tours de Hanoï;
- trouver le chemin pour qu'un cavalier parcourre toutes les cases d'un échiquier, une et une seule fois;
- placer huit reines sur un échiquier sans qu'elles ne se mettent en échec (voir l'exemple);
- recherche d'itinéraire.

Source / Exemple :


'Remarque: il y a une et une seule reine par colonne,
'          le numéro de reine est donc confondu avec son numéro de colonne
'Résumé:   on cherche une ligne pour placer la reine numéro iReine,
'          si on y parvient
'               si c'est la dernière, on a terminé
'               sinon, on cherche à placer la suivante
'          sinon, il faut déplacer la reine précédente
Private Function PlacerReine(ByVal iReine As Integer) As Boolean
Dim iLigne                                  As Integer
Dim bRetour                                 As Boolean
    For iLigne = 0 To 7
        If Not bLigneOccupee(iLigne) _
        And Not bDiagonaleMontanteOccupee(iLigne + iReine) _
        And Not bDiagonaleDescendanteOccupee(7 + iReine - iLigne) Then
            bLigneOccupee(iLigne) = True
            bDiagonaleMontanteOccupee(iLigne + iReine) = True
            bDiagonaleDescendanteOccupee(7 + iReine - iLigne) = True
            Animation iLigne, iReine, True
            If iReine = 7 Then
                bRetour = True
            Else
                bRetour = PlacerReine(iReine + 1)
            End If
            If bRetour Then Exit For
            bLigneOccupee(iLigne) = False
            bDiagonaleMontanteOccupee(iLigne + iReine) = False
            bDiagonaleDescendanteOccupee(7 + iReine - iLigne) = False
            Animation iLigne, iReine, False
        End If
    Next iLigne
    PlacerReine = bRetour
End Function

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

neamar
Messages postés
26
Date d'inscription
vendredi 9 septembre 2005
Statut
Membre
Dernière intervention
12 avril 2009
-
Salutations,
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.
mstarsup5
Messages postés
527
Date d'inscription
lundi 15 octobre 2007
Statut
Membre
Dernière intervention
10 octobre 2013
-
Salut, ayant moi même fait des programmes en récursif, et ayant cherché à voir leur fonctionnement en itératif, je ne peux qu'aller dans le sens de la remarque de BruNews: d'un point de vue performance, les procédés itératifs sont bien meilleurs. (J'arrivais parfois à avoir des gains en vitesse d'exécution de l'ordre de 400%... ce qui, comme tu peux le constater, n'est pas négligeable.)

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.
cs_jupiter
Messages postés
34
Date d'inscription
lundi 5 août 2002
Statut
Membre
Dernière intervention
9 janvier 2009
-
Bonjour,
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.
lucqum
Messages postés
3
Date d'inscription
lundi 20 novembre 2006
Statut
Membre
Dernière intervention
15 avril 2009
-
A Brunews,

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.
BruNews
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
13 -
L' "élégance" est à confronter à:
- 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.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.