Récursivité
Cours · informatique (MP2I/MPI), chapitre 5 · MP2I et MPI · le début du chapitre, la suite sur Adloun
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.
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
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.
(* É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.
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 — 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 ».
À 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é.