Récursivité : les Tours de Hanoi en JavaScript

Dans cet article, nous allons résoudre le problème des tours de Hanoï en utilisant la récursivité.

1. Quel est le principe des tours de Hanoï ?

Les tours de Hanoï est un problème posé par le mathématicien français Edouard LUCAS.

Trois tiges (tours) peuvent contenir des disques de diamètres différents. Initialement, tous les disques sont sur la même tours à gauche, du plus large au plus étroit.
Le but est de déplacer les disques de la première à la troisième en respectant le même ordre des disques selon les règles suivantes :

  • Un seul disque ne peut être déplacé à la fois.
  • Un disque ne peut être posé que sur un disque plus large.

Résoudre se problème avec un algorithme procédural est extrêmement compliqué, pourtant en utilisant la récursivité  le problème devient trivial.

La récursivité est basée sur le principe d’une fonction qui s’appelle elle-même. La difficulté est de comprendre les étapes engendrées et si une fin à l’algorithme est prévue.

2. Résolution du problème des tours de Hanoï par récursivité

  • On part de l’état initial ci-dessous, formé du disque du bas(bleu) surmonté de l’empilement des autres disques (rouge). On appelle la fonction hanoi(n, a, b, c) pour passer les disques à droite. n étant le nombre de disque et a, b et c, les tours.
  • Dans un premier temps on fait passer la pile de n-1 éléments au milieu, pour pouvoir sortir le disque “bleu” du dessous. C’est ce que fait l’appel récursif hanoi(n-1, a, c, b), pour faire passer les n-1 premiers disques au milieu (on inverse b et c pour indiquer qu’ondéplace les éléments au milieu). On dit que c’est un appel récursif, car c’est la fonction hanoi(…) qui s’appelle elle même.
  • On fait passer ensuite l’élément du bas sur la troisième tour (code JavaScript). document.write (a + “vers” + c”);
  • On termine en faisant passer le tas du milieu sur l’élément que l’on vient de poser sur la troisième tour. Pour ce faire, on appelle la fonction hanoi(n-1, b, a, c) récursivement.

Et voilà la récursivité fait le reste. Génial non ?

  • Le code Javascript récursif des tours de Hanoi.

Voici le code javascript :

1
2
3
4
5
6
7
8
9
10
11
<script language="JavaScript" type="text/javascript">
var n = 3;
function hanoi(n, a=1, b=2, c =3){
if(n>0){
hanoi(n-1, a, c, b);
document.write(a + "vers" + c + "<br/>");
hanoi(n-1, b, a, c);
}
}
hanoi(n)
</script>

Pour tester, cliquer sur les liens :
HANOI 3 pièces
HANOI 4 pièces
HANOI 5 pièces

J’espère que ce petit tutoriel sur la récursivité vous aura intéressé.

A bientôt sur Outils Web

Partager