%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Récursivité/Récursivité|Accueil · Récursivité]]
%% nav-fin %%
# Les Tours de Hanoï
## 🎯 Objectif
Mettre en œuvre une **fonction récursive** permettant de résoudre un problème par **décomposition en sous-problèmes similaires**.
## 📄 Énoncé
On dispose de **trois tiges** :
- `A` : tige de départ
- `B` : tige intermédiaire
- `C` : tige d’arrivée
et de `n` disques empilés sur la tige `A`, du plus grand (en bas) au plus petit (en haut).
### Règles
- On ne déplace **qu’un disque à la fois**.
- On ne peut jamais poser un disque **plus grand sur un disque plus petit**.
L’objectif est de **déplacer toute la pile de la tige A vers la tige C**.
## 🔎 Observer avant de programmer
**À manipuler :** déplacez vous-même les disques de A vers C. Le composant refuse les coups interdits et compte vos coups.
```sq-hanoi
n: 3
mode: manuel
```
**À manipuler :** suivez la solution récursive. Chaque étape montre le déplacement et la pile des appels `hanoi` en cours.
```sq-hanoi
n: 3
```
## 🧩 Travail demandé
Les cellules Python de cette page s'exécutent dans le navigateur. Le premier clic sur « Exécuter » charge Python, ce qui prend quelques secondes. La correction est cachée sous chaque question.
### Question 1 : afficher les déplacements
Le problème se résout récursivement en trois étapes :
1. déplacer les n − 1 disques du haut de `debut` vers `inter` ;
2. déplacer le dernier disque de `debut` vers `fin` ;
3. déplacer les n − 1 disques de `inter` vers `fin`.
Écrivez la fonction `hanoi(n, debut, inter, fin)`. Elle reçoit le nombre de disques et le nom des trois tiges : départ, intermédiaire, arrivée. Elle affiche chaque déplacement sous la forme `A C`, qui signifie : un disque passe de la tige A à la tige C.
L'appel `hanoi(3, 'A', 'B', 'C')` déplace d'abord 2 disques de A vers B, donc il appelle `hanoi(2, 'A', 'C', 'B')`. Quand il ne reste qu'un disque, la fonction affiche le déplacement : c'est la condition d'arrêt.
```sq-python
def hanoi(n, debut, inter, fin):
pass # à compléter
hanoi(3, 'A', 'B', 'C')
#--- correction
def hanoi(n, debut, inter, fin):
if n == 1:
print(debut, fin)
else:
hanoi(n - 1, debut, fin, inter)
print(debut, fin)
hanoi(n - 1, inter, debut, fin)
hanoi(3, 'A', 'B', 'C')
#--- sortie
A C
A B
C B
A C
B A
B C
A C
```
Comparez votre sortie à la solution pas à pas du composant ci-dessus : les sept déplacements sont les mêmes.
### Question 2 : nombre minimal de déplacements
Écrivez une fonction récursive `nb_deplacements(n)` qui renvoie le nombre de déplacements effectués par `hanoi` pour `n` disques.
Déplacer n disques demande deux fois le déplacement de n − 1 disques, plus le déplacement du plus grand. Avec 0 disque, il n'y a aucun déplacement.
```sq-python
def nb_deplacements(n):
pass # à compléter
print([nb_deplacements(n) for n in range(1, 11)])
#--- correction
def nb_deplacements(n):
if n == 0:
return 0
return 2 * nb_deplacements(n - 1) + 1
print([nb_deplacements(n) for n in range(1, 11)])
#--- tests
assert nb_deplacements(1) == 1, "Un seul disque se déplace en un coup."
assert nb_deplacements(3) == 7, "Trois disques demandent 7 déplacements."
assert nb_deplacements(10) == 1023, "Dix disques demandent 1023 déplacements."
assert all(nb_deplacements(n) == 2 ** n - 1 for n in range(15)), "Le résultat doit valoir 2 puissance n, moins 1."
#--- sortie
[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
```
### Question 3 (bonus) : afficher et compter
Modifiez `hanoi` pour qu'elle affiche les déplacements et renvoie leur nombre. La fonction s'appelle ici `hanoi_compte`.
```sq-python
def hanoi_compte(n, debut, inter, fin):
pass # à compléter
print(hanoi_compte(3, 'A', 'B', 'C'))
#--- correction
def hanoi_compte(n, debut, inter, fin):
if n == 1:
print(debut, fin)
return 1
nb = hanoi_compte(n - 1, debut, fin, inter)
print(debut, fin)
nb = nb + 1 + hanoi_compte(n - 1, inter, debut, fin)
return nb
print(hanoi_compte(3, 'A', 'B', 'C'))
#--- sortie
A C
A B
C B
A C
B A
B C
A C
7
```
## 🧠 À retenir
- Une fonction récursive repose toujours sur :
- un **cas de base**,
- un **appel à elle-même** sur un problème plus simple.
- Pour `n` disques, le nombre minimal de déplacements est :
**2ⁿ − 1**.
%% nav-debut : généré par gen_navigation.py, ne pas modifier à la main %%
> [!nav]
> ↩ [[Code et Développement/Programmation/Récursivité/Récursivité|Accueil · Récursivité]]
%% nav-fin %%
---
🗓️ Historique
Dernière mise à jour : `05 février 2026`
Rédigé par : [[Julien DUQUENNOY]]