Récursivité et retour sur trace

Cours complet · OCaml (option informatique), chapitre 11 · prépas MPSI et MP, option informatique

Travailler ce chapitre sur Adloun Exercices corrigés de ce chapitre

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>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.

Complexité : Coût exponentiel, profondeur linéaire

Le nombre de coups vérifie $C (n) = 2 C (n - 1) + 1$ , soit $C (n) = 2^{n} - 1$ : exponentiel. Pourtant la profondeur de récursion n'est que $n$ : un même petit programme engendre un travail gigantesque. C'est typique des récursions multiples — à manier en sachant que le coût peut exploser.

11.3 Énumérer par récursion

11.3.1 Les parties d'un ensemble

Engendrer toutes les sous-listes (les parties) d'une liste : pour chaque partie du reste, on a deux choix — y inclure la tête, ou non. D'où un doublement à chaque élément.


let rec parties l =
  match l with
  | [] -> [[]]
  | x :: reste ->
      let sous = parties reste in
      sous @ List.map (fun s -> x :: s) sous

parties [1; 2] renvoie [[]; [2]; [1]; [1; 2]]. Une liste de $n$ éléments a $2^{n}$ parties : l'énumération est nécessairement exponentielle. (List.map est rappelé au chapitre 2 ; on l'utilise ici pour préfixer x à chaque sous-partie.)

11.3.2 Les permutations

Engendrer tous les ordonnancements d'une liste demande un outil : insérer un élément à toutes les positions d'une liste.


let rec aplatis ll =          (* concatène une liste de listes *)
  match ll with
  | [] -> []
  | l :: reste -> l @ aplatis reste

let rec insere_partout x l =
  match l with
  | [] -> [[x]]
  | t :: reste ->
      (x :: l) :: List.map (fun p -> t :: p) (insere_partout x reste)

let rec permutations l =
  match l with
  | [] -> [[]]
  | x :: reste ->
      aplatis (List.map (insere_partout x) (permutations reste))

insere_partout x l liste les façons de glisser x dans l ; permutations insère le premier élément partout dans chaque permutation du reste. Il y a $n!$ permutations : encore une explosion combinatoire. (On réécrit aplatis à la main, la concaténation de listes de listes n'étant pas au programme.)

11.4 Le retour sur trace

Méthode : Le schéma du backtracking

Pour explorer un arbre de choix :

si la configuration courante est une solution, la signaler ;
sinon, pour chaque choix possible : le poser, explorer récursivement, et — si l'on utilise un état mutable — le retirer avant d'essayer le choix suivant.

En OCaml fonctionnel, on passe le nouvel état (une liste enrichie, un compteur) en argument de l'appel récursif : l'ancien restant intact, le retour arrière est gratuit. L'opérateur paresseux || permet de s'arrêter dès qu'une solution est trouvée.

Exemple 11.1Somme d'un sous-ensemble

Existe-t-il un sous-ensemble de l de somme cible (entiers positifs) ? À chaque élément, deux choix : le prendre ou non.


let rec existe_somme l cible =
  if cible = 0 then true
  else
    match l with
    | [] -> false
    | x :: reste ->
        existe_somme reste (cible - x)   (* on prend x *)
        || existe_somme reste cible      (* on ne prend pas x *)

On explore l'arbre binaire des choix. Le || paresseux abandonne la seconde branche dès qu'une solution est trouvée dans la première : c'est l'élagage le plus simple.

11.5 Les $n$ reines

Placer $n$ reines sur un échiquier $n \times n$ sans qu'aucune n'en menace une autre : c'est le problème-étalon du backtracking. On place une reine par colonne, en mémorisant les lignes déjà occupées.


let n_reines n =
  (* compatible : la ligne candidate ne menace aucune reine déjà posée ;
     'distance' = écart de colonnes avec la reine la plus récente. *)
  let rec compatible ligne reines distance =
    match reines with
    | [] -> true
    | l :: reste ->
        l <> ligne
        && l - ligne <> distance
        && ligne - l <> distance
        && compatible ligne reste (distance + 1)
  in
  let rec place col reines =
    if col = n then 1                     (* toutes les colonnes placées : 1 solution *)
    else begin
      let total = ref 0 in
      for ligne = 0 to n - 1 do
        if compatible ligne reines 1 then
          total := !total + place (col + 1) (ligne :: reines)
      done;
      !total
    end
  in
  place 0 []

place essaie chaque ligne pour la colonne courante ; si elle est compatible avec les reines déjà posées (ni même ligne, ni même diagonale), on descend d'une colonne en ajoutant cette reine. n_reines 8 renvoie 92.

iRemarqueLe retour arrière est automatique

On ne « retire » jamais explicitement une reine : à l'appel place (col + 1) (ligne :: reines), on construit une nouvelle liste ligne :: reines ; la liste reines courante n'est pas modifiée, et reste disponible pour essayer la ligne suivante dans la boucle. L'immuabilité fait le retour sur trace pour nous.

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>11.6 Exercices résolus

Niveau $⋆$ (application directe du cours)

Exercice 1 : Nombre de coups de Hanoï

Écrire nb_coups n (sans construire la liste des coups) et établir nb_coups n $= 2^{n} - 1$ .

Démonstration


let rec nb_coups n =
  if n = 0 then 0
  else 2 * nb_coups (n - 1) + 1

Par récurrence : $C (0) = 0 = 2^{0} - 1$ ; et $C (n) = 2 C (n - 1) + 1 = 2 (2^{n - 1} - 1) + 1 = 2^{n} - 1$ . Déplacer $64$ disques demanderait $2^{64} - 1$ coups : astronomique.

Exercice 2 : Les parties

Écrire parties et vérifier qu'une liste de $n$ éléments produit $2^{n}$ parties.

Démonstration


let rec parties l =
  match l with
  | [] -> [[]]
  | x :: reste ->
      let sous = parties reste in
      sous @ List.map (fun s -> x :: s) sous

À chaque élément, on double le nombre de parties (celles sans x, et les mêmes avec x en tête). Partant de [[]] ( $1$ partie pour la liste vide), on obtient $2^{n}$ : parties [1; 2; 3] en a $8$ .

Exercice 3 : Sous-ensemble de somme donnée

Écrire existe_somme l cible (entiers positifs) et l'appliquer à existe_somme [2; 3; 7] 5.

Démonstration


let rec existe_somme l cible =
  if cible = 0 then true
  else
    match l with
    | [] -> false
    | x :: reste ->
        existe_somme reste (cible - x) || existe_somme reste cible

existe_somme [2;3;7] 5 : prendre 2 puis chercher 3 dans [3;7] → prendre 3, cible 0 → true. Le sous-ensemble ${2, 3}$ convient.

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Exercice 4 : Liste des coups de Hanoï

Écrire hanoi produisant la liste des déplacements, et donner hanoi 2 "A" "B" "C".

Démonstration


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 2 "A" "B" "C" $=$ [("A","B"); ("A","C"); ("B","C")] : on pose le petit disque en B, le grand en C, puis le petit en C. Trois coups, comme $2^{2} - 1$ .

Exercice 5 : Permutations

Écrire permutations (à l'aide de insere_partout et aplatis) et compter celles de [1; 2; 3].

Démonstration


let rec insere_partout x l =
  match l with
  | [] -> [[x]]
  | t :: reste ->
      (x :: l) :: List.map (fun p -> t :: p) (insere_partout x reste)

let rec permutations l =
  match l with
  | [] -> [[]]
  | x :: reste ->
      aplatis (List.map (insere_partout x) (permutations reste))

permutations [1;2;3] en compte $3! = 6$ . Pour chaque permutation du reste, on glisse x aux k+1 positions possibles, d'où la multiplication par la longueur croissante.

Exercice 6 : Compter les sous-ensembles de somme donnée

Modifier existe_somme en compte_somme l cible qui compte le nombre de sous-ensembles de somme cible.

Démonstration


let rec compte_somme l cible =
  if cible = 0 then 1
  else if cible < 0 then 0
  else
    match l with
    | [] -> 0
    | x :: reste ->
        compte_somme reste (cible - x) + compte_somme reste cible

On remplace le « trouvé / pas trouvé » (||) par une addition des deux sous-comptes : avec x, sans x. Le cas cible = 0 compte $1$ (l'ensemble construit convient) ; cible < 0 compte $0$ (on a dépassé).

Exercice 7 : Combinaisons

Écrire combinaisons k l : toutes les sous-listes de l à exactement k éléments.

Démonstration


let rec combinaisons k l =
  if k = 0 then [[]]
  else
    match l with
    | [] -> []
    | x :: reste ->
        List.map (fun c -> x :: c) (combinaisons (k - 1) reste)  (* avec x *)
        @ combinaisons k reste                                    (* sans x *)

Même dichotomie de choix que parties, mais en contraignant la taille : prendre x (il reste k-1 à choisir) ou non (toujours k à choisir). Les cas de base : k = 0 (une seule combinaison, vide) et liste vide avec k > 0 (aucune). On obtient $(k n)$ combinaisons.

Niveau $⋆ ⋆ ⋆$ (approfondissement)

Exercice 8 : Les

n

reines

Écrire n_reines n comptant le nombre de placements valides, et donner n_reines 4 et n_reines 8.

Démonstration


let n_reines n =
  let rec compatible ligne reines distance =
    match reines with
    | [] -> true
    | l :: reste ->
        l <> ligne && l - ligne <> distance && ligne - l <> distance
        && compatible ligne reste (distance + 1)
  in
  let rec place col reines =
    if col = n then 1
    else begin
      let total = ref 0 in
      for ligne = 0 to n - 1 do
        if compatible ligne reines 1 then
          total := !total + place (col + 1) (ligne :: reines)
      done;
      !total
    end
  in
  place 0 []

n_reines 4 $= 2$ , n_reines 8 $= 92$ . La fonction compatible vérifie, en remontant les colonnes (distance croissante), qu'aucune reine n'est sur la même ligne ni sur l'une des deux diagonales. L'élagage (on ne descend que si compatible) rend l'exploration praticable.

Exercice 9 : Reconstruire le sous-ensemble

Écrire trouve_somme l cible : int list option qui renvoie un sous-ensemble de somme cible (et pas seulement son existence), ou None.

Démonstration


let rec trouve_somme l cible =
  if cible = 0 then Some []
  else
    match l with
    | [] -> None
    | x :: reste ->
        match trouve_somme reste (cible - x) with
        | Some s -> Some (x :: s)            (* x fait partie de la solution *)
        | None -> trouve_somme reste cible   (* sinon, chercher sans x *)

On essaie d'abord de prendre x : si la suite réussit, on l'ajoute à la solution rapportée ; sinon, on cherche sans lui. Le type option porte à la fois l'échec (None) et la solution reconstruite (Some s) — le backtracking « remonte » la solution le long des choix réussis.

Exercice 10 : Sortie d'un labyrinthe

Un labyrinthe est une matrice de booléens (true = mur). Écrire accessible laby qui teste si l'on peut aller du coin (0,0) au coin (n-1,m-1) par déplacements orthogonaux.

Démonstration


let accessible laby =
  let n = Array.length laby and m = Array.length laby.(0) in
  let vu = Array.make_matrix n m false in
  let rec explore i j =
    if i < 0 || i >= n || j < 0 || j >= m then false
    else if laby.(i).(j) || vu.(i).(j) then false
    else if i = n - 1 && j = m - 1 then true
    else begin
      vu.(i).(j) <- true;
      explore (i + 1) j || explore (i - 1) j
      || explore i (j + 1) || explore i (j - 1)
    end
  in
  explore 0 0

On explore en profondeur, en marquant les cases visitées (vu) pour ne pas tourner en rond : c'est ici l'état mutable du backtracking. On renvoie true dès qu'on atteint la sortie (le || élague les autres directions). Inutile de « démarquer » : pour la simple accessibilité, une case déjà explorée sans succès le restera. (Marquer évite une récursion infinie entre deux cases voisines.)

Synthèse du chapitre (à retenir)

Récursivité multiple (Hanoï) : profondeur linéaire, mais travail exponentiel possible ( $C (n) = 2^{n} - 1$ ).
Énumérer : parties ( $2^{n}$ , par doublement), permutations ( $n!$ , par insertion partout), combinaisons ( $(k n)$ ). L'explosion combinatoire est inhérente.
Retour sur trace : essayer chaque choix, explorer, défaire si besoin. Schéma : solution ? sinon, pour chaque choix : poser / explorer / (retirer). || paresseux pour s'arrêter à la première solution.
En OCaml fonctionnel, passer un nouvel état (liste enrichie) à l'appel récursif rend le retour arrière automatique (immuabilité) — cf. les $n$ reines. Avec un état mutable (matrice vu du labyrinthe), on marque ; on défait seulement si le problème l'exige.
option permet de reconstruire une solution (Some s) le long des choix réussis, pas seulement de la détecter.

11.7 Exercices d'entraînement

Légende : $⋆$ application directe, $⋆ ⋆$ raisonnement intermédiaire, $⋆ ⋆ ⋆$ approfondissement ; $⧫$ signale un classique incontournable. La numérotation prolonge celle des dix exercices résolus.

Thème A — Récursivité multiple.

[11.] $⋆$ Écrire fibo n en double récursion, et expliquer son coût exponentiel (lien avec le chapitre 8 : la mémoïsation).
[12.] $⋆ ⋆$ Modifier hanoi pour qu'elle affiche chaque coup (print_string) au lieu de renvoyer une liste.
[13.] $⋆ ⋆ ⋆$ Écrire nb_chemins n m : le nombre de chemins monotones (droite/bas) d'un coin à l'autre d'une grille $n \times m$ , par récursion.

Thème B — Énumération.

[14.] $⋆ ⋆$ Écrire sous_listes_taille k l sans combinaisons (réécrire le raisonnement).
[15.] $⋆ ⋆$ $⧫$ Écrire produit_cartesien l1 l2 : tous les couples (x, y) avec x dans l1, y dans l2.
[16.] $⋆ ⋆ ⋆$ Engendrer tous les mots binaires de longueur n (listes de 0/1).

Thème C — Backtracking.

[17.] $⋆ ⋆$ Écrire partition_egale l : peut-on couper l en deux sous-ensembles de même somme ?
[18.] $⋆ ⋆ ⋆$ Adapter n_reines pour renvoyer une solution (liste des lignes) plutôt que les compter.
[19.] $⋆ ⋆ ⋆$ $⧫$ Rendu de monnaie : compter le nombre de façons de faire une somme avec des pièces de valeurs données (chaque valeur réutilisable).

Thème D — Sur grille.

[20.] $⋆ ⋆ ⋆$ Modifier accessible pour compter le nombre de cases atteignables depuis (0,0).
[21.] $⋆ ⋆ ⋆$ Trouver un chemin (liste de cases) de l'entrée à la sortie d'un labyrinthe, et le renvoyer en option.
[22.] $⋆ ⋆ ⋆$ $⧫$ Discuter : pourquoi marquer les cases visitées est-il indispensable, et que change-t-il si l'on cherche tous les chemins plutôt qu'un seul ?

Continuer sur Adloun : animation, QCM, fiches, exercices

Récursivité et retour sur trace

<i class="fa-solid fa-compass mr-2" style="color:#9A563B"></i>11.1 Introduction et motivation

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

Complexité : Coût exponentiel, profondeur linéaire

11.3 Énumérer par récursion

11.3.1 Les parties d'un ensemble

11.3.2 Les permutations

11.4 Le retour sur trace

Méthode : Le schéma du backtracking

11.5 Les n reines

<i class="fa-solid fa-dumbbell mr-2" style="color:#2E7559"></i>11.6 Exercices résolus

Niveau ⋆ (application directe du cours)

Niveau ⋆⋆ (raisonnement intermédiaire)

Niveau ⋆⋆⋆ (approfondissement)

11.7 Exercices d'entraînement

Thème A — Récursivité multiple.

Thème B — Énumération.

Thème C — Backtracking.

Thème D — Sur grille.

11.5 Les $n$ reines

Niveau $⋆$ (application directe du cours)

Niveau $⋆ ⋆$ (raisonnement intermédiaire)

Niveau $⋆ ⋆ ⋆$ (approfondissement)