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éﬁnition
Déﬁnition 4 (Déﬁnition récursive, algorithme récursif). Une déﬁnition récursive est une déﬁnition dans laquelle intervient ce que l’on veut déﬁnir. Un algorithme est dit récursif lorsqu’il est déﬁni 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éﬁnition récursive est beaucoup plus générale : en mathématiques : déﬁnition de l’exponentielle :∀x∈R, f0(x)= f(x) et f(0)= 1. en programmation : déﬁnition en Ocaml d’une liste inﬁnie 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éﬁnie 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éﬁnition 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éﬁnitions sont dites mutuellement récursives si elles dépendent les unes des autres. Ça peut être le cas pour la déﬁnition 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éﬁnie 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. Difﬁcultés : – la déﬁnition 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éﬁnie, c’est-à-dire, qu’elle est déﬁnie 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éﬁnition soit strictement monotone et ﬁnit toujours par atteindre une valeur pour laquelle la solution est explicitement déﬁnie. 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 ﬁnit toujours pas aboutir à un couple d’arguments (a,b) tel que b−a est négatif, cas déﬁni 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éﬁni 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..