Cours : algorithmes et récursivité
Pour tous ceux qui s'intéressent aux algorithmes dont notamment la récursivité, je signale un lien exceptionnel à lire absolument :
http://recursivite.developpez.com
On peut y télécharger au format PDF un livre complet (145 pages!) d'Axel Chambily-Casadesus et Petrut Constantine sur le sujet :
http://recursivite.developpez.com/recursivite.pdf
Ce manuel traite un nombre impressionnant d'algorithmes (anagrammes, fractales, tris, arbres et graphes, dictionnaire, parcours du fou sur un échiquier, problème des tours de Hanoi, jeu du compte est bon, dérécursificaton etc..), itérativement puis grâce à la récursivité.
:arrow: A titre de complément au livre, voici ci-dessous deux algorithmes récursifs "génériques".
Pour les appliquer, il suffit de bien visualiser l'enchaînement des cas possibles et de bien définir la condition d'arrêt et le vecteur d'état. Les exemples du livre ont pour objectif de préciser ces données en fonction de leur contexte afin d'optimiser le traitement...
1- Algorithme de recherche à essais successifs (backtracking) : modélisation de la recherche par arbre ; arrêt à la première solution trouvée.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
Essai (Etape)
-------------
Repeter ...
{
Selection etape racine du sous-arbre suivant
Si étape acceptable alors ..
{
Sauvegarde du vecteur d'état
Enregistrement étape
Si Non_Succès (vecteur d'état) alors ..
{
Essai(racine_sous_arbre)
Si Non_Succès (vecteur d'état) alors ..
{
Annulation de l'enregistrement de l'étape
Restauration du vecteur d'état
}
}
}
}
Jusqu'à Succès (vecteur d'état) OU (plus de sous-arbres)
Fin. |
2- Algorithme de recherche à essais successifs de toutes les solutions.
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
Essai (Etape)
-------------
Pour tous les sous-arbres ..
{
Selection etape racine du sous-arbre suivant
Si étape acceptable alors ..
{
Sauvegarde du vecteur d'état
Enregistrement étape
Si Non_Succès (vecteur d'état) alors ..
{
Essai(racine_sous_arbre)
sinon enregistrer la solution
}
Annulation de l'enregistrement de l'étape
Restauration du vecteur d'état
}
}
Fin. |
Voilà : en espérant que cela vous éclairera autant que moi :wink:
ftp://ftp-developpez.com/recursivite/recursivite.pdf: Lien mort
