Récursivité

Cours complet · informatique (MP2I/MPI), chapitre 5 · MP2I et MPI

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

5.1 Se définir par soi-même

Pour décrire un escalier, deux phrases sont possibles. « Une suite de marches » : c'est la boucle. « Une marche, puis un escalier plus petit » : c'est la récursivité. Les deux décrivent le même objet ; la seconde le décrit en s'appuyant sur lui-même, et s'arrête parce que l'escalier finit par n'avoir plus de marches.

Le programme place cette idée très haut : « la capacité d'un programme à faire appel à lui-même est un concept primordial en informatique. Historiquement, l'auto-référence est au cœur du paradigme de programmation fonctionnelle. » Et il pose une limite nette : « on se limite à une présentation pratique de la récursivité comme technique de programmation », et « toute théorie générale de la dérécursification est hors programme ». On apprend donc à s'en servir, à la prouver et à en payer le prix — pas à la théoriser.

AttentionNi factorielle, ni Fibonacci

Le programme est explicite : « on évite de se limiter à des exemples informatiquement peu pertinents (factorielle, suite de Fibonacci, …) ». Ces deux exemples-là s'écrivent mieux avec une boucle, et donnent la fausse impression que la récursivité n'est qu'une boucle déguisée. Ce chapitre les cite pour analyser leur coût, jamais pour les recommander.

5.2 Le principe

Définition 5.1Fonction récursive

Une fonction est récursive si son corps contient un appel à elle-même. Toute définition récursive correcte comporte :

un ou plusieurs cas de base, résolus sans appel ;
un ou plusieurs cas récursifs, où la solution s'exprime à partir de la solution du même problème sur une entrée strictement plus petite.

En OCaml, le mot-clé rec est obligatoire pour qu'une fonction se voie elle-même ; en C, rien n'est à déclarer.

Exemple 5.2Un exemple qui vaut la peine : le rendu de monnaie en pièces binaires


(* Écrit n en binaire, du bit de poids fort au bit de poids faible.
   Précondition : n >= 0. *)
let rec binaire n =
  if n < 2 then string_of_int n
  else binaire (n / 2) ^ string_of_int (n mod 2)

La version à boucle existe, mais elle doit construire la chaîne à l'envers puis la retourner : la récursion, elle, produit les bits dans le bon ordre sans effort, parce que la remontée des appels renverse naturellement l'ordre de la descente. C'est cela, un bon exemple de récursivité : un problème où elle simplifie.

Méthode : Concevoir une fonction récursive : trois questions

Le cas de base. Pour quelles entrées la réponse est-elle immédiate ?
La décomposition. Si l'on me donnait la solution pour une entrée plus petite, comment en déduirais-je la mienne ?
La décroissance. Chaque appel rapproche-t-il strictement d'un cas de base ?

Le point 2 est le saut : on fait confiance à l'appel récursif, comme on fait confiance à l'hypothèse de récurrence — sans dérouler mentalement les appels. Le point 3 est le variant du chapitre chap:algo-prog, et c'est lui qui prouve la terminaison.

Définition 5.3Récursivité croisée

Deux fonctions peuvent s'appeler l'une l'autre. En OCaml, elles se déclarent ensemble avec and :


(* pair n et impair n disent la parité de n. Précondition : n >= 0. *)
let rec pair n   = if n = 0 then true  else impair (n - 1)
and     impair n = if n = 0 then false else pair   (n - 1)

Le variant est le même pour les deux — $n$ décroît strictement à chaque appel — et c'est ce qui prouve que le va-et-vient s'arrête.

5.3 Ce que fait la machine : la pile d'exécution

Le programme insiste : « on met l'accent sur la gestion au niveau de la machine, en termes d'occupation mémoire, de la pile d'exécution, et de temps de calcul, en évoquant les questions de sauvegarde et de restauration de contexte ».

Définition 5.4Bloc d'activation

À chaque appel, la machine empile un bloc d'activation contenant les paramètres, les variables locales et l'adresse de retour. Au retour, le bloc est dépilé et l'exécution reprend chez l'appelant, dans le contexte restauré.

AttentionLe débordement de pile

La pile a une taille bornée, et les deux langages n'ont pas du tout la même marge. Mesuré sur une récursion non terminale, avec la pile par défaut de $8$ Mio :

	Profondeur atteinte	Ce qui arrive ensuite
C, `-O0`	quelques centaines de milliers	violation de segment, brutale
OCaml	quelques dizaines de millions	exception `Stack_overflow`

Une profondeur de $1 0^{6}$ tue donc un programme C et ne gêne pas OCaml, dont la pile s'étend. L'écart tient à la gestion de la mémoire, pas au langage : ne transposez jamais d'un langage à l'autre une limite mesurée sur l'un.

Retenez donc qu'une fonction récursive a un coût en espace égal à sa profondeur de récursion, même si elle n'alloue rien. Une récursion sur un tableau de $n$ cases traité un élément à la fois est $O (n)$ en espace ; la même en dichotomie est $O (lo g n)$ .

Définition 5.5Arbre des appels

Quand une fonction s'appelle plusieurs fois, les activations ne forment plus une chaîne mais un arbre — le programme demande explicitement l'« organisation des activations sous forme d'arbre en cas d'appels multiples ».

Ci-dessus, l'arbre des appels de fib 4. On y voit fib 2 calculé deux fois et fib 1 trois fois : c'est le chevauchement des sous-problèmes, et c'est ce qui rend cette récursion exponentielle. La programmation dynamique du chapitre chap:dynamique n'existe que pour supprimer ce gâchis.

Attention à ne pas confondre : la hauteur de cet arbre est la profondeur de pile ( $O (n)$ ), tandis que son nombre de nœuds est le temps de calcul ( $O (φ^{n})$ ). Deux grandeurs, deux coûts.

5.4 Prouver une fonction récursive

Méthode : Terminaison par variant, correction par récurrence

Terminaison : exhiber une quantité entière positive qui décroît strictement à chaque appel récursif. C'est le variant, transposé de la boucle à l'appel.
Correction : récurrence sur ce même variant. On suppose la fonction correcte sur toutes les entrées de variant strictement plus petit, et l'on montre qu'elle l'est sur l'entrée courante.

Exemple 5.6Exponentiation rapide, prouvée


(* puissance x n renvoie x^n. Précondition : n >= 0. *)
let rec puissance x n =
  if n = 0 then 1
  else
    let m = puissance x (n / 2) in
    if n mod 2 = 0 then m * m else m * m * x

Démonstration

Terminaison. Variant : $n$ . Pour $n \geq 1$ , l'appel se fait sur $⌊ n /2 ⌋ < n$ , et $n$ reste positif. La suite des variants est strictement décroissante et minorée : elle est finie.

Correction, par récurrence forte sur $n$ . Base : $n = 0$ , la fonction rend $1 = x^{0}$ . Hérédité : soit $n \geq 1$ , et supposons la fonction correcte pour tout $k < n$ . Alors $m = x^{⌊ n /2 ⌋}$ par hypothèse.

Si $n$ est pair, $n = 2 ⌊ n /2 ⌋$ , et $m \times m = x^{2 ⌊ n /2 ⌋} = x^{n}$ .
Si $n$ est impair, $n = 2 ⌊ n /2 ⌋ + 1$ , et $m \times m \times x = x^{2 ⌊ n /2 ⌋ + 1} = x^{n}$ .

Dans les deux cas la valeur rendue est $x^{n}$ .

Complexité. Le variant est divisé par deux à chaque appel : la profondeur est $Θ (lo g n)$ , et chaque niveau coûte $O (1)$ multiplication. Donc $Θ (lo g n)$ multiplications, contre $Θ (n)$ pour la méthode naïve. Pour $n = 1 0^{9}$ : trente multiplications au lieu d'un milliard.

5.5 Les récurrences de complexité

Définition 5.7Les trois formes du programme

Le programme nomme trois récurrences, « introduites au fur et à mesure de l'étude de la complexité des différents algorithmes rencontrés » :

$T (n) = T (n - 1) + an, T (n) = a T (n /2) + b, T (n) = 2 T (n /2) + f (n) .$

Et il pose une consigne de méthode : « on utilise des encadrements élémentaires ad hoc afin de les justifier ; on évite d'appliquer un théorème-maître général ». Le théorème-maître est donc hors programme : chaque récurrence se résout à la main.

Exemple 5.8

T (n) = T (n - 1) + an

: le tri par sélection

En déroulant :

$T (n) = an + a (n - 1) + \dots + a \cdot 1 + T (0) = a \frac{n ( n + 1 )}{2} + T (0) = Θ (n^{2}) .$

Exemple 5.9

T (n) = a T (n /2) + b

: la dichotomie, et son coût

Pour $a = 1$ — un seul appel récursif, comme la recherche dichotomique — il y a $lo g_{2} n$ niveaux, chacun coûtant $b$ :

$T (n) = T (n /2) + b = T (n /4) + 2 b = \dots = T (1) + b lo g_{2} n = Θ (lo g n) .$

Pour $a = 2$ — deux appels, comme un parcours d'arbre complet — le nombre d'appels double à chaque niveau : il y en a $1 + 2 + 4 + \dots + 2^{l o g_{2} n} = 2 n - 1$ , d'où $T (n) = Θ (n)$ .

Exemple 5.10

T (n) = 2 T (n /2) + f (n)

: diviser pour régner

Avec $f (n) = c n$ — le tri par partition-fusion : chaque niveau traite $n$ éléments au total, et il y a $lo g_{2} n$ niveaux :

D'où $T (n) = Θ (n lo g n)$ — le résultat le plus utile de tout ce livre, et il s'obtient en comptant des rectangles.

5.6 Récursion terminale

Définition 5.11Appel terminal

Un appel récursif est terminal lorsqu'il est la dernière chose que fait la fonction : son résultat est rendu tel quel, sans calcul après lui.


(* NON terminal : il reste « x * ... » à faire APRÈS l'appel. *)
let rec produit = function [] -> 1 | x :: r -> x * produit r

(* Terminal : l'appel est la dernière opération, l'accumulateur porte le calcul. *)
let produit_t l =
  let rec aux acc = function [] -> acc | x :: r -> aux (acc * x) r in
  aux 1 l

Dans le second cas, rien ne reste à faire au retour : le compilateur OCaml peut réutiliser le bloc d'activation courant au lieu d'en empiler un nouveau. La récursion s'exécute alors en espace $O (1)$ , comme une boucle.

iRemarqueCe n'est pas de la dérécursification

La théorie générale de la dérécursification est hors programme, et la récursion terminale n'en est pas : c'est une propriété de la forme d'une fonction, que le compilateur exploite. On la connaît pour deux raisons pratiques : elle explique pourquoi certaines fonctions récursives ne débordent jamais la pile, et elle justifie le style à accumulateur, très fréquent en OCaml.

AttentionLe compilateur C n'en donne aucune garantie

gcc sait faire cette optimisation, mais rien dans la norme ne l'y oblige, et elle disparaît sans les options d'optimisation.

Et elle va plus loin qu'on ne l'attend, ce qui rend la dépendance plus inquiétante encore : mesuré sur ce livre, une somme récursive non terminale — où il reste un n + à faire au retour — meurt à $1 0^{7}$ appels sous -O0 et passe sans broncher sous -O2, l'optimiseur ayant reconnu l'accumulation. Le même source vit ou meurt selon une option de ligne de commande, y compris quand l'appel n'est pas terminal. En C, une récursion profonde reste donc un risque ; on y préfère souvent la boucle explicite.

5.7 Ce qu'il faut retenir

ImportantRécursivité : les quatre points de contrôle

Un cas de base, atteint par tout appel — c'est le variant qui le garantit.
Une décomposition en sous-problème strictement plus petit, à laquelle on fait confiance.
Un coût en espace égal à la profondeur de pile, même sans allocation.
Un coût en temps donné par le nombre de nœuds de l'arbre des appels — que l'on obtient en résolvant la récurrence à la main, jamais par un théorème-maître.

Le chapitre chap:induction montrera que ces raisonnements se généralisent : le variant devient un ordre bien fondé, et la récurrence une induction structurelle — ce qui permettra de prouver des fonctions sur les arbres et sur les formules logiques exactement comme on vient de le faire sur les entiers.

Continuer sur Adloun : animation, QCM, fiches, exercices