Récursivité : Analyse recursive

Pour résoudre un problème de manière récursive, on réalise une anlyse recursive.

Etape 1, Recherche d'un cas trivial : celui qui peut être résolu sans appel récursif (le critère d’arrêt) ; 

Étape 2, Paramétrage du problème : déterminer les paramètres en particulier la taille qui doit décroître a chaque appel récursif (converger vers le cas trivial);

Étape 3, Décomposition du cas général : ramener la résolution du problème a la résolution d'un ou de plusieurs problèmes de même nature et de taille plus petite (la partie récursive);

 

Exemple : Tour de Hanoї [Lucas 1883]:

Problème : 64 disques étant posés les uns sur les autres par ordre de taille décroissant sur un socle A, les transférer sur un socle B en utilisant un socle C en ne prenant qu'un disque a la fois pour le déposer sur un disque plus grand.

Réponse :

1. Analyse recursive

Étape 1 : avoir un seul disque (i.e. n=1) est un cas trivial car il suffit de le déplacer directement depuis le socle de départ vers le socle d’arrivée. D’où le critère d’arrêt :

si n=1 alors déplacer un disque du socle A vers le socle B

Étape 2 : n est le nombre de disques, socle de départ, socle d’arrivée et socle intermédiaire sont les paramètres. D’où : Action Hanoi(E/ n : entier ; E/ depart,arrivee,intermed : socle ) ;

Étapes 3 : Un socle contenant un disque plus grand que tous les autres est assimilable pour le transfert de ceux ci a une position vide. D’où la décomposition :

n disques peuvent être transférés de A vers B en :

• transférant n-1 disques de A vers C en utilisant B comme intermédiaire;
• déplacer le disque restant de A vers B ;
• transférant les n-1 disques de C vers B en utilisant A comme intermédiaire.

2. Algorithme

Action deplacer (E/x,y:caractere);

debut 

       ecrire('Deplacer un disque du socle',x,'vers le socle',y);

fin ;

Action Hanoi(E/ n:entier ; E/ x,y,z : caractere) ;

debut

    si n=1 alors

        deplacer(x,y) ;

    sinon

        Hanoi(n-1,x,z,y) ;

        deplacer(x,y) ;

        Hanoi(n-1,z,y,x) ;

    fsi ;

fin ;

Algorithme TourHanoi ;

debut

    Hanoi(64,'A','B','C') ;

fin.

3. En résumé [fom Wikipedia]:

« The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions. »  Niklaus Wirth, Algorithms + Data Structures = Programs.

«  La puissance de la récursivité réside évidemment dans la possibilité de définir des ensembles infinis d'objets par une affirmation finie. De façon similaire, un nombre infini d'étapes de calcul peut être décrit par un programme récursif fini, même si ce programme ne contient aucune répétition explicite. »

Bibliography and/or further reading:

1. Meyer B. et Baudoin C., Méthodes de programmation. Eyrolles 1984.

2. http://en.wikipedia.org/wiki/Tower_of_Hanoi

3. http://www.fil.univ-lille1.fr/~sedoglav/C/main019.html