Tours de Hanoï

L'algorithme classique des tours de Hanoï résout le problème en déplaçant $n$ disques de la manière suivante :

def hanoi(n, source, cible, auxiliaire):
    if n == 1:
        print(f"Déplacer {source} -> {cible}")
    else:
        hanoi(n-1, source, auxiliaire, cible)
        print(f"Déplacer {source} -> {cible}")
        hanoi(n-1, auxiliaire, cible, source)

• Établir la relation de récurrence du nombre de déplacements $D(n)$.

• Résoudre cette récurrence et démontrer que $D(n)=2^n-1$.

• Déterminer la complexité temporelle et spatiale.