Tours de Hanoi

Les tours de Hanoï sont un célèbre casse tête inventé par Édouard Lucas.

Il consiste à déplacer $n$ disques de diamètres différents d'une tour de "départ" à une tour d' "arrivée" en passant par une tour "intermédiaire", tout en respectant les règles suivantes :

On suppose que cette dernière règle est également respectée dans la configuration de départ.

Une interface pour jouer aux tours de Hanoï.

Déplacez les cylindres par glisser/déposer.

Essayons de résoudre ce problème de façon optimale.

Donnez un algorithme récursif permettant de résoudre le problème.

Quelle est sa complexité ?

Peut-on faire mieux ?