Les tours de Hanoï

[ retour page d'accueil | source | programme sans la fonction récursive ]

Cette appliquette déplace n disques de la pile de gauche vers la pile de droite en utilisant la fonction récursive suivante :

deplace (n, org, tmp, dest)
si (n > 0)
    deplace (n-1, org, dest, tmp)
    déplace un disque de org vers dest
     deplace (n-1, tmp, org, dest)
finsi

On démontre aisément que le nombre un de déplacements de n disques est défini par
u1 = 1 et un = 2 un - 1 + 1 puis que pour tout entier n strictement positif un = 2n - 1.