Analyse
On va imaginer, afin de ramener le problème à un nombre de disques plus petit, que l'on sait faire passer tous les disques sauf le dernier, d'un pilier à un autre. On a donc diminué de un le nombre de disques à déplacer.
C'est le principe de la récursivité : on va définir le problème à partir d'un problème similaire d'ordre inférieur (comme pour la fonction factorielle n!=n*(n-1)! ou la fonction puissance xn = x * xn - 1).
Pour déplacer n disques de la tour 1 à la tour 3 :
-
déplacer n - 1 disques de la tour 1 à la tour 2 « (on suppose qu'on sait le faire) »
-
déplacer 1 disque de la tour 1 à la tour 3 « (on sait le faire : il ne reste plus qu'un seul disque) »
-
déplacer n - 1 disques de la tour 2 à la tour 3 « (même supposition qu'au début : on sait le faire) »
