Programmation

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 ce 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é par l’empilement des n-1 autres disques (rouge).
    La fonction hanoi(n, a = 1, b = 2, c = 3) est appelée pour faire passer tous les disques de gauche à droite, c’est-à-dire de la tour a = 1 à la tour c = 3, où n étant le nombre de disques et a, b et c, les tours.
  • La fonction hanoi(n, a, b, c) contient la fonction hanoi(n-1, a, c, b). la fonction s’appelle elle-même, avec d’autres arguments, c’est un appel récursif, en inversant le rôle de b et de c. cet appel demande de faire passer la pile de n-1 éléments de gauche (en rouge) au milieu. Il reste le disque “bleu” du dessous sur la première tour a.
  • On fait passer ensuite l’élément bleu du bas de la première tour a = 1 sur la troisième tour c = 3. Cette fois le code s’écrit explicitement (code JavaScript). document.write (a + “vers” + c”);
    a et c sont des paramètres pouvant prendre chacun les valeurs 1, 2 ou 3, numéro des trois tours.
  • On termine en faisant passer le tas de n-1 éléments de la tour du milieu b = 2 sur l’élément bleu que l’on vient de poser sur la troisième tour. Pour ce faire, on appelle récursivement la fonction hanoi(n-1, b, a, c). n-1 indique le nombre d’éléments à déplacer, et on inverse les rôles de a et b pour indiquer que ce sont les éléments du milieu ui vont à droite.

La suite, c’est la récursivité qui le fait.

En gros on décrit les premières étapes nécessaires et ensuite demande de continuer ainsi, la récursivité s’occupe des différentes étapes. Génial non ?

Une dernière chose très importante, il faut une condition d’arrêt, pour que les appels récursifs ne soient pas infinis, c’est la condition if(n > 0) du programme qui joue ce rôle. S’il reste des disques, on continue.

  • 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