La tour de Hanoï est presque toujours l’exemple choisi pour apprendre la « récursivité » en programmation. À la main, il faut des centaines de coups, mais en programme, quelques lignes suffisent. Voyons comment cela marche, pas à pas. Les tiges sont la gauche, la centrale et la droite ; les disques sont numérotés 1, 2, 3… du plus petit au plus grand.
Qu’est-ce que la récursivité
La récursivité, c’est réutiliser, dans la méthode qui résout un problème, la même méthode sur un problème plus petit. En rapetissant le problème, on finit par arriver à un cas dont la réponse est immédiate (par exemple, avec 0 disque, on ne fait rien), et là, on s’arrête.
Penser la tour de Hanoï de façon récursive
Considérons le déplacement d’une tour de n disques de la gauche vers la droite.
- Déplacer les n − 1 disques du haut de la gauche vers le milieu.
- Déplacer le plus grand disque, n, de la gauche vers la droite.
- Déplacer les n − 1 disques du milieu vers la droite.
Les étapes 1 et 3 sont des problèmes « déplacer une tour de n − 1 disques », de même forme que le problème de départ. Seules les tiges de départ et d’arrivée changent. Il suffit donc d’écrire une méthode « déplacer n disques d’une tige à une autre en utilisant la tige restante », qui peut s’appeler elle-même.
Pseudo-code
procédure hanoi(n, départ, arrivée, auxiliaire):
si n vaut 0, ne rien faire et terminer
hanoi(n − 1, départ, auxiliaire, arrivée) … écarter les n−1 disques du haut
déplacer le disque n de « départ » à « arrivée »
hanoi(n − 1, auxiliaire, arrivée, départ) … remettre les n−1 disques
hanoi(3, gauche, droite, milieu) donne les coups pour 3 disques, de la gauche vers la droite Avec cela seul, on obtient la solution en nombre minimal de coups pour n’importe quel nombre de disques. Du vrai code Python et C qui fonctionne est présenté dans Résoudre la tour de Hanoï en Python et en C.
L’arbre des appels
Pour 3 disques, si l’on écrit comment hanoi est appelé, on obtient un arbre comme celui-ci. Plus une ligne est en retrait, plus l’appel est imbriqué.
hanoi(3, gauche→droite)
├─ hanoi(2, gauche→milieu)
│ ├─ hanoi(1, gauche→droite) … 1 à droite
│ ├─ 2 au milieu
│ └─ hanoi(1, droite→milieu) … 1 au milieu
├─ 3 à droite
└─ hanoi(2, milieu→droite)
├─ hanoi(1, milieu→gauche) … 1 à gauche
├─ 2 à droite
└─ hanoi(1, gauche→droite) … 1 à droite La suite des « déplacements » lue de haut en bas est exactement la solution en 7 coups. Un appel en produit deux autres à l’intérieur, donc le travail double presque à chaque disque en plus.
Complexité
| Ce qu’on regarde | Pour n disques |
|---|---|
| Nombre de déplacements (coups) | 2ⁿ − 1 |
| Nombre d’appels de hanoi (en comptant les appels à 0 disque) | 2ⁿ⁺¹ − 1 |
| Profondeur des appels (ce qu’il faut garder en mémoire en même temps) | n + 1 niveaux |
La raison pour laquelle il y a 2ⁿ − 1 coups est démontrée dans la formule du nombre minimal de coups. Le temps croît de façon exponentielle avec le nombre de disques (O(2ⁿ)), alors que la mémoire à garder est simplement proportionnelle au nombre de disques (O(n)). Comme il y a 2ⁿ − 1 coups en tout, quelle que soit l’astuce, écrire toute la solution prend ce temps-là.
Sans récursivité
On peut aussi résoudre le problème avec de simples boucles, sans récursivité. C’est exactement la méthode à la main présentée dans l’article sur la façon de résoudre le jeu.
procédure hanoi_boucle(n):
choisir le sens du disque 1 (si n est impair : gauche→droite→milieu ; si n est pair : gauche→milieu→droite)
répéter pour coup = 1, 2, 3, … , 2ⁿ − 1 :
si coup est impair, déplacer le disque 1 sur la tige suivante dans le sens choisi
si coup est pair, comparer les disques du haut des deux tiges qui ne portent pas le 1,
et déplacer le plus petit sur le plus grand (ou sur une tige vide) Comme il n’y a pas d’appels à garder en mémoire, la mémoire utilisée est très faible.
En binaire, trouver directement n’importe quel coup
Il existe même une méthode pour trouver directement ce qu’il faut faire au coup numéro m, sans refaire les coups précédents. Numérotons les tiges 0, 1 et 2. Pour le coup m (compté à partir de 1) :
- le disque à déplacer est le disque numéro (nombre de 0 à la fin de m écrit en binaire) + 1 ;
- la tige de départ est le reste de la division de (m AND (m − 1)) par 3 ;
- la tige d’arrivée est le reste de la division de ((m OR (m − 1)) + 1) par 3.
AND et OR sont les opérations « et » et « ou » appliquées chiffre binaire par chiffre binaire. Par exemple, pour m = 4 (100 en binaire), il y a 2 zéros à la fin, donc le disque est le numéro 3 ; le départ est (4 AND 3) = 0, donc la tige 0 ; l’arrivée est ((4 OR 3) + 1) = 8, et le reste de 8 divisé par 3 donne la tige 2.
Les coups obtenus par ces formules déplacent les disques de la tige 0 à la tige 2 si le nombre de disques est impair, et de la tige 0 à la tige 1 s’il est pair. Pour viser la tige 2 avec un nombre pair de disques, on lit en échangeant les tiges 1 et 2. Ce lien entre le nombre de coups et le binaire est détaillé dans l’article sur les régularités.
