Programmation récursive

Résumé en cinq points

1Récursivité

1.1Fonction récursive

let rec factorielle n =
  if n = 0 then 1 else n * factorielle (n - 1)

Sur les listes, la récursivité suit la structure du type : cas de la liste vide et cas d'une tête suivie d'une queue.

let rec longueur l = match l with
  | [] -> 0
  | _ :: q -> 1 + longueur q

1.2Récursivité croisée

let rec est_pair n = if n = 0 then true else est_impair (n - 1)
and est_impair n = if n = 0 then false else est_pair (n - 1)

On rencontre la récursivité croisée dans deux cas :

• l'analyse d'expressions : une expression contient des termes, qui contiennent des facteurs, qui peuvent contenir des expressions ;
• les types mutuellement récursifs.

1.3Pile d'exécution et activations

L'appel factorielle 4 empile les activations pour 4, 3, 2, 1 et 0, puis les dépile en effectuant les multiplications au retour.

On obtient souvent cette forme en ajoutant un accumulateur.

let factorielle n =
  let rec aux n acc =
    if n = 0 then acc else aux (n - 1) (n * acc) in
  aux n 1

1.4Organisation des activations sous forme d'arbre en cas d'appels multiples

Quand une fonction fait plusieurs appels récursifs, les activations ne forment plus une simple suite mais un arbre, l'arbre des appels. Chaque nœud est un appel, ses fils sont les appels qu'il déclenche. L'exemple type est la suite de Fibonacci écrite naïvement.

let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2)

L'arbre des appels de fib 5 a pour racine fib 5, qui a pour fils fib 4 et fib 3, et ainsi de suite. Le même sous-calcul, fib 3 par exemple, apparaît plusieurs fois.

Lire l'arbre des appels, c'est à la fois comprendre l'ordre d'exécution, qui est un parcours en profondeur de cet arbre, et estimer le coût.

2Récursivité et principe de récurrence

2.1Prouver la correction par récurrence

Une fonction récursive se prouve par récurrence sur la taille de son argument. On montre que le résultat est correct dans les cas de base, puis que si les appels récursifs renvoient des résultats corrects, l'appel courant aussi.

Pour les listes, on raisonne par récurrence sur la longueur, ou par induction structurelle, point développé au chapitre sur les types récursifs.

Exemple plus riche : la fusion de deux listes triées, écrite dans la section sur le tri par partition-fusion.

La preuve de correction suit exactement la structure du programme, c'est l'intérêt principal de la récursivité.

2.2Terminaison

Pour factorielle, l'argument entier naturel décroît de 1.

2.3Ordre bien fondé

L'ensemble des entiers naturels muni de l'ordre usuel est bien fondé, celui des entiers relatifs ne l'est pas.

C'est la généralisation de la récurrence à tout ordre bien fondé (récurrence bien fondée). Le programme demande d'insister sur ce lien avec les relations d'ordre.

Il prouve la terminaison de fonctions où aucune composante seule ne décroît toujours.

3Stratégie diviser pour régner

3.1Principe

Diviser pour régner résout un problème en trois temps :

1. Diviser l'entrée en sous-problèmes du même type et de taille nettement plus petite, typiquement la moitié ;
2. Résoudre récursivement chaque sous-problème ;
3. Combiner les solutions pour obtenir celle du problème initial.

Le programme demande de ne pas se limiter à des exemples où la décomposition et la recomposition sont évidentes.

3.2Tri par partition-fusion

On coupe la liste en deux moitiés, on trie chacune récursivement, puis on fusionne les deux listes triées en parcourant leurs têtes.

let rec fusion l1 l2 = match l1, l2 with
  | [], l | l, [] -> l
  | x :: q1, y :: q2 ->
      if x <= y then x :: fusion q1 l2
      else y :: fusion l1 q2

Le partage se fait en distribuant les éléments un sur deux dans deux listes, puis tri l = fusion (tri l1) (tri l2), avec pour cas de base les listes de longueur 0 ou 1.

let rec partage l = match l with
  | [] -> [], []
  | [x] -> [x], []
  | x :: y :: q -> let a, b = partage q in x :: a, y :: b

let rec tri l = match l with
  | [] | [_] -> l
  | _ -> let a, b = partage l in fusion (tri a) (tri b)

Pour une liste de longueur $n \geqslant 2$, les deux moitiés ont des longueurs $\lceil n/2 \rceil$ et $\lfloor n/2 \rfloor$, toutes deux strictement inférieures à $n$.

• La fusion de deux listes de longueurs $p$ et $q$ coûte au plus $p + q$ comparaisons.
• Le partage coûte un parcours de la liste.

3.3Exemples moins immédiats

• Exponentiation rapide. $x^n = (x^{n/2})^2$ si $n$ est pair, $x \times (x^{(n-1)/2})^2$ sinon. Un seul appel récursif sur $n$ divisé par 2, à condition de ne calculer $x^{n/2}$ qu'une fois.
• Multiplication de Karatsuba. Pour multiplier deux entiers de $n$ chiffres, on les coupe en deux moitiés, $x = aB + b$ et $y = cB + d$. Le produit demande $ac$, $bd$ et $ad + bc$. On calcule ce dernier comme $(a+b)(c+d) - ac - bd$, soit trois multiplications de taille $n/2$ au lieu de quatre.
• Points les plus proches dans le plan. La combinaison demande d'examiner une bande autour de la droite de séparation. C'est l'exemple où la recomposition est la vraie difficulté.

4Analyse de la complexité des algorithmes récursifs

4.1Relations de récurrence sur le coût

Le coût $C(n)$ d'une fonction récursive vérifie une relation qui reproduit sa structure. On la résout sur chaque exemple, en déroulant la relation ou en raisonnant sur l'arbre des appels, sans théorème général, qui n'est pas au programme. On étudie la complexité dans le pire cas.

• Factorielle. $C(n) = C(n-1) + 1$, donc $C(n)$ est de l'ordre de $n$.
• Exponentiation rapide. $C(n) = C(n/2) + O(1)$, donc $C(n)$ est de l'ordre de $\log n$.
• Karatsuba. $C(n) = 3\,C(n/2) + O(n)$. Le niveau $i$ de l'arbre a $3^i$ nœuds de taille $n/2^i$, et le dernier niveau domine, d'où un coût de l'ordre de $n^{\log_2 3}$, soit environ $n^{1{,}585}$, contre $n^2$ pour la méthode scolaire.
• Fibonacci naïf. $C(n) = C(n-1) + C(n-2) + O(1)$, coût exponentiel, $C(n) = \Theta(\varphi^n)$.

4.2Autres analyses, en moyenne et amortie

Le programme demande seulement de sensibiliser, sur des exemples, à l'existence d'autres analyses que le pire cas.

• La complexité en moyenne fait la moyenne du coût sur toutes les entrées d'une taille donnée, pour une loi de probabilité fixée. Le tri rapide a un coût de l'ordre de $n^2$ dans le pire cas mais de l'ordre de $n \log n$ en moyenne sur les permutations équiprobables.
• La complexité amortie mesure le coût moyen d'une opération sur une suite d'opérations. Ajouter un élément à un tableau dynamique qui double sa capacité quand il est plein coûte parfois de l'ordre de $n$, lors d'une recopie, mais le coût total de $n$ ajouts reste de l'ordre de $n$, soit un coût amorti constant.

Méthodes

Ce qu'il faut savoir refaire en khôlle

1. Écrire en OCaml une fonction récursive sur les entiers et une sur les listes, avec filtrage, et prouver leur correction par récurrence.
2. Définir deux fonctions mutuellement récursives et expliquer l'usage de let rec ... and ....
3. Dessiner l'arbre des appels de la fonction de Fibonacci naïve et en déduire le nombre d'appels et la hauteur de pile.
4. Définir un ordre bien fondé, montrer que l'ordre lexicographique sur les couples d'entiers naturels l'est, et prouver la terminaison de la fonction d'Ackermann.
5. Écrire le tri par partition-fusion sur les listes, établir la relation de coût et justifier le coût de l'ordre de $n \log n$.
6. Présenter l'idée de Karatsuba, établir sa relation de coût et comparer à la multiplication naïve.
7. Donner un exemple de complexité en moyenne et un exemple de complexité amortie.

Les résultats à connaître

Le chapitre contient surtout des méthodes de preuve et des coûts de référence, à savoir établir sur chaque exemple.

• Principe de terminaison. Si le corps termine hors appels récursifs, et si chaque appel porte sur un argument strictement plus petit pour un ordre bien fondé, alors tout appel termine. Exigible avec démonstration.
• Un ordre est bien fondé si et seulement si toute partie non vide admet un élément minimal. Exigible, preuve esquissée.
• N muni de l'ordre usuel est bien fondé. Admis, c'est le cours de mathématiques.
• L'ordre lexicographique sur N², et sur N^k, est bien fondé. Exigible avec démonstration.
• L'ordre lexicographique sur les mots d'un alphabet d'au moins deux lettres n'est pas bien fondé. Contre-exemple exigible.
• Correction. Elle se prouve par récurrence simple, forte ou bien fondée sur la mesure de terminaison. Méthode exigible.
• Fusion de deux listes triées de longueurs p, q ≥ 1. Le résultat est trié, avec au plus p + q − 1 comparaisons. Exigible avec démonstration.
• Tri par partition-fusion. Il est correct, avec O(n log n) comparaisons dans le pire cas. Exigible avec démonstration.
• Exponentiation rapide. Elle fait O(log n) multiplications. Exigible avec démonstration.
• Karatsuba. Son coût est O(n^{log₂ 3}). Exigible sur l'exemple, par l'arbre des appels.
• Fibonacci naïf. Il fait 2F(n + 1) − 1 appels, où F est la suite de Fibonacci, et la pile atteint une hauteur d'ordre n. Exigible avec démonstration.
• Appel terminal. OCaml n'empile pas de nouvelle activation. Admis, c'est un comportement du compilateur.
• Tri rapide. Il est quadratique dans le pire cas et en O(n log n) en moyenne. Sensibilisation, le résultat en moyenne est admis.
• Hors programme : théorème général des relations de récurrence (« théorème maître »), dérécursification générale, classes de complexité.

Clés de démonstration

Principe de terminaison. Si un appel ne termine pas, l'un de ses sous-appels ne termine pas non plus, puisque le corps termine hors appels. Ce sous-appel porte sur un argument strictement plus petit. En itérant, on obtient une suite infinie strictement décroissante, ce qui est impossible. Astuce : suivre la chaîne des appels qui ne terminent pas.

Ordre lexicographique sur N². Soit (a_k, b_k) une suite strictement décroissante. La suite des a_k décroît au sens large dans N, donc elle est stationnaire à partir d'un rang K. Au-delà, ce sont les b_k qui décroissent strictement dans N, contradiction. Astuce : une suite décroissante d'entiers naturels est stationnaire.

Correction du tri fusion. On raisonne par récurrence forte sur la longueur n. Pour n ≥ 2, les moitiés ont des longueurs ⌈n/2⌉ et ⌊n/2⌋, strictement inférieures à n, donc elles sont triées par hypothèse. La correction de la fusion conclut. Astuce : la récurrence forte est nécessaire, car on ne passe pas de n − 1 à n.

Coût du tri fusion pour n quelconque. On montre par récurrence forte que le coût maximal C est croissant. Si 2^k−1 < n ≤ 2^k, alors C(n) ≤ C(2^k) = O(k·2^k) = O(n log n). Astuce : se ramener aux puissances de 2 par monotonie.

Appels de Fibonacci. On a A(0) = A(1) = 1 et A(n) = 1 + A(n − 1) + A(n − 2). Avec B(n) = A(n) + 1, on obtient B(n) = B(n − 1) + B(n − 2) et B(0) = B(1) = 2, donc B(n) = 2F(n + 1). Astuce : ajouter la constante qui rend la relation homogène.

Karatsuba. Pour n = 2^k, le niveau i compte 3ⁱ nœuds de travail proportionnel à n/2ⁱ. Le total est proportionnel à n·Σ(3/2)ⁱ pour i de 0 à k, somme majorée par 3·(3/2)^k. D'où C(n) = O(3^k) = O(n^{log₂ 3}). Astuce : dans une somme géométrique de raison supérieure à 1, le dernier terme domine.

Exemples et contre-exemples à connaître

1. Suite de Syracuse. On écrit sans peine la fonction qui compte les étapes jusqu'à 1, mais personne ne sait prouver qu'elle termine toujours. La terminaison n'est pas une formalité.
2. Fonction 91 de McCarthy : f(n) = n − 10 si n > 100, f(f(n + 11)) sinon. Elle vaut 91 pour n ≤ 100, alors que l'argument croît d'abord. La preuve utilise la mesure 101 − n et établit la valeur en même temps.
3. Une décrémentation jusqu'à 0 ne termine pas sur un entier négatif. Z n'est pas bien fondé, la spécification doit fixer le domaine.
4. Les mots b, ab, aab, aaab, … décroissent strictement pour l'ordre lexicographique. Cet ordre n'est pas bien fondé sur les mots.
5. Sans le cas de base [_], le tri fusion boucle sur une liste à un élément. La preuve de terminaison détecte le bug.
6. Renverser une liste avec @ coûte de l'ordre de n², avec un accumulateur de l'ordre de n. L'opérateur @ n'est pas en temps constant.
7. Écrire puissance x (n / 2) * puissance x (n / 2) redonne un coût linéaire. Deux appels identiques annulent le gain.
8. Le tri rapide avec la tête comme pivot est quadratique sur une liste déjà triée. Le pire cas peut être l'entrée la plus banale.
9. Euclide, pgcd a b = pgcd b (a mod b), termine avec la mesure b et coûte un temps logarithmique. C'est une récursion sur les entiers qui n'est pas une décrémentation.
10. A(4, 2) = 2⁶⁵⁵³⁶ − 3 pour Ackermann, soit plus de dix-neuf mille chiffres. Terminer ne veut pas dire terminer vite.

Techniques du chapitre

Technique 1 : écrire la relation avant le code. Nombre de chiffres décimaux de n ≥ 1 : c(n) = 1 si n < 10, 1 + c(n / 10) sinon, avec la division entière. Code : let rec chiffres n = if n < 10 then 1 else 1 + chiffres (n / 10). La mesure n décroît strictement dans N, car n / 10 < n.

Technique 2 : généraliser l'énoncé pour un accumulateur. Soit aux [] acc = acc et aux (x :: q) acc = aux q (acc + x). On prouve « pour tout acc, aux l acc = acc + somme de l » par récurrence sur la longueur. L'hérédité donne acc + x + somme q. L'énoncé doit porter sur tout acc.

Technique 3 : nommer la mesure. Pour pgcd a b avec a, b ≥ 0, la mesure est b ∈ N. Si b > 0, l'appel porte sur (b, a mod b) avec 0 ≤ a mod b < b. La mesure décroît strictement, donc la fonction termine.

Technique 4 : récurrence forte pour les appels sur n/2. Soit f n = if n = 0 then 0 else 1 + f (n / 2). Pour n ≥ 1, n / 2 < n et son écriture binaire est celle de n privée du dernier bit. La récurrence forte montre que f n est le nombre de bits de n.

Technique 5 : lire le coût sur l'arbre. Pour C(1) = 0 et C(n) = 2C(n/2) + 1 avec n = 2^k, le niveau i compte 2ⁱ nœuds de coût 1, pour i de 0 à k − 1. Donc C(n) = 2^k − 1 = n − 1.

Technique 6 : sommer une série géométrique décroissante. Pour C(1) = 1 et C(n) = C(n/2) + n, on déroule : C(n) = n + n/2 + … + 1 < 2n. Le premier niveau domine, le coût est linéaire.

Technique 7 : supprimer les calculs répétés en renvoyant un couple. On calcule (F(n), F(n + 1)) à partir de (F(n − 1), F(n)), avec un seul appel par niveau (exercice 3).

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

let rec renverse_naif l = match l with
  | [] -> []
  | x :: q -> renverse_naif q @ [x]

let renverse l =
  let rec aux l acc = match l with
    | [] -> acc
    | x :: q -> aux q (x :: acc) in
  aux l []

let rec puissance x n =
  if n = 0 then 1
  else
    let y = puissance x (n / 2) in
    if n mod 2 = 0 then y * y else x * y * y

let fib n =
  let rec aux n =
    if n = 0 then (0, 1)
    else let a, b = aux (n - 1) in (b, a + b) in
  let a, _ = aux n in a

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

let rec u n = if n = 0 then 1 else u (n - 1) + 2 * v (n - 1)
and v n = if n = 0 then 1 else u (n - 1) + v (n - 1)

let rec uv n =
  if n = 0 then (1, 1)
  else let a, b = uv (n - 1) in (a + 2 * b, a + b)

let rec coupe l k = if k = 0 then [], l else match l with
  | [] -> [], []
  | x :: q -> let a, b = coupe q (k - 1) in x :: a, b

let rec fusion l1 l2 n1 = match l1, l2 with
  | [], l | l, [] -> l, 0
  | x :: q1, y :: q2 ->
      if x <= y then let r, c = fusion q1 l2 (n1 - 1) in x :: r, c
      else let r, c = fusion l1 q2 n1 in y :: r, c + n1

let rec inv l n =
  if n <= 1 then l, 0
  else
    let a, b = coupe l (n / 2) in
    let ta, ia = inv a (n / 2) in
    let tb, ib = inv b (n - n / 2) in
    let t, ic = fusion ta tb (n / 2) in
    t, ia + ib + ic

let rec incr l = match l with
  | [] -> [1]
  | 0 :: q -> 1 :: q
  | _ :: q -> 0 :: incr q

Erreurs fréquentes