Cours : algorithmes et récursivité

**Community Management** · 07/02/2003, 17h49

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é.

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.