Algorithmique avancée

Algorithmique avancée

La récursivité et le paradigme « diviser pour régner »

Récursivité
De l’art d’écrire des programmes qui résolvent des problèmes que l’on ne sait pas résoudre soi-même !

Définition
Définition 4 (Définition récursive, algorithme récursif). Une définition récursive est une définition dans laquelle intervient ce que l’on veut définir. Un algorithme est dit récursif lorsqu’il est défini en fonction de lui-même.
Dans le cadre de ce cours, nous ne nous intéresserons qu’aux programmes et algorithmes récursifs. Mais la notion de définition récursive est beaucoup plus générale : en mathématiques : définition de l’exponentielle :∀x∈R, f0(x)= f(x) et f(0)= 1. en programmation : définition en Ocaml d’une liste infinie dont tous les éléments valent 1 :
let rec z = 1::z;;
Récursivité simple Revenons à la fonction puissance x7→xn. Cette fonction peut être définie récursivement : xn = 1 si n = 0; x×xn−1 si n≥1. L’algorithme correspondant s’écrit :
PUISSANCE (x, n) Si n = 0 alors renvoyer 1 sinon renvoyer x×PUISSANCE(x, n−1)
3.1.3 Récursivité multiple Une définition récursive peut contenir plus d’un appel récursif. Nous voulons calculer ici les combinaisons Cp n en se servant de la relation de Pascal :
Cp n = 1 si p = 0 ou p = n; Cp n−1 +Cp−1 n−1 sinon.
L’algorithme correspondant s’écrit :
COMBINAISON (n, p) Si p = 0 ou p = n alors renvoyer 1 sinon renvoyer COMBINAISON (n−1, p) + COMBINAISON (n−1, p−1) Bref, rien de particulier…
Récursivité mutuelle
Des définitions sont dites mutuellement récursives si elles dépendent les unes des autres. Ça peut être le cas pour la définition de la parité : pair(n)= vrai si n = 0; impair(n−1) sinon; et impair(n)= faux si n = 0; pair(n−1) sinon. Les algorithmes correspondants s’écrivent : PAIR (n) Si n = 0 alors renvoyer vrai sinon renvoyer IMPAIR (n−1) IMPAIR (n) Si n = 0 alors renvoyer faux sinon renvoyer PAIR (n−1)
Récursivité imbriquée
La fonction d’Ackermann est définie comme suit : A(m,n)=   n+1 si m = 0 A(m−1,1) si m > 0 et n = 0 A(m−1,A(m,n−1)) sinon d’où l’algorithme : ACKERMANN(m, n) si m = 0 alors n+1 sinon si n = 0 alors ACKERMANN(m−1, 1) sinon ACKERMANN(m−1, ACKERMANN(m, n−1))
En résumé : on peut utiliser la récursivité comme l’on veut, à peu près n’importe comment…
Principe et dangers de la récursivité
Principe et intérêt : ce sont les mêmes que ceux de la démonstration par récurrence en mathématiques. On doit avoir : – un certain nombre de cas dont la résolution est connue, ces « cas simples » formeront les cas d’arrêt de la récursion; – un moyen de se ramener d’un cas « compliqué » à un cas « plus simple ». La récursivité permet d’écrire des algorithmes concis et élégants. Difficultés : – la définition peut être dénuée de sens : Algorithme A(n) renvoyer A(n) – il faut être sûrs que l’on retombera toujours sur un cas connu, c’est-à-dire sur un cas d’arrêt; il nous faut nous assurer que la fonction est complètement définie, c’est-à-dire, qu’elle est définie sur tout son domaine d’applications. Moyen : existence d’un ordre strict tel que la suite des valeurs successives des arguments invoqués par la définition soit strictement monotone et finit toujours par atteindre une valeur pour laquelle la solution est explicitement définie. L’algorithme ci-dessous teste si a est un diviseur de b.
DIVISEUR (a,b) Si a≤0 alors Erreur sinon si a≥b alors a = b (test d’égalité) sinon DIVISEUR(a,b−a)
La suite des valeurs b, b−a, b−2×a, etc. est strictement décroissante, car a est strictement positif, et on finit toujours pas aboutir à un couple d’arguments (a,b) tel que b−a est négatif, cas défini explicitement. Cette méthode ne permet pas de traiter tous les cas :
SYRACUSE(n) Si n = 0 ou n = 1 alors 1 sinon si n mod 2 = 0 alors SYRACUSE (n/2) sinon SYRACUSE (3×n+1) Problème ouvert : l’algorithme est bien défini et vaut 1 sur N. Question : N’y a-t-il vraiment aucun moyen de déterminer automatiquement si un algorithme récursif quelconque va terminer? Réponse à la section suivante..