Récursivité: placer huit reines sur un échiquier
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.
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
- Récursivité: placer huit reines sur un échiquier
- Recursivite java - Forum Java
- Recursivité en c - Conseils pratiques -PHP
- Recursivite python - Forum Python
- Recursivité ✓ - Forum C# / .NET
- Récursivité ??? - Forum Delphi / Pascal
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.