Récursivité et retour sur trace

11.1 Introduction et motivation

La récursion a jusqu'ici servi à parcourir des structures (listes, arbres) ou à diviser un problème en deux (tri fusion, dichotomie). Ce chapitre l'emploie pour explorer un espace de possibilités : énumérer toutes les configurations d'un problème, ou en chercher une qui satisfasse une contrainte. C'est le domaine du retour sur trace (backtracking) — essayer un choix, poursuivre, et revenir en arrière si l'on aboutit à une impasse.

On commence par la récursivité multiple (plusieurs appels récursifs) avec les tours de Hanoï, puis l'énumération (parties, permutations), et enfin le backtracking proprement dit (somme d'un sous-ensemble, les $n$ reines, un labyrinthe). Un fil conducteur, propre à OCaml : comme les valeurs sont immuables, passer un nouvel état à l'appel récursif suffit souvent — le retour arrière est alors automatique, sans rien à défaire.

11.2 Récursivité multiple : les tours de Hanoï

Déplacer $n$ disques d'un piquet à un autre, sans jamais poser un grand disque sur un plus petit, se résout par une élégante récursion à deux appels : déplacer les $n-1$ disques du dessus sur le piquet intermédiaire, bouger le grand disque, puis ramener les $n-1$ disques.

let rec hanoi n depart inter arrivee =
  if n = 0 then []
  else
    hanoi (n - 1) depart arrivee inter
    @ [(depart, arrivee)]
    @ hanoi (n - 1) inter depart arrivee

hanoi 3 "A" "B" "C" renvoie la liste des déplacements (couples de piquets) résolvant le problème.