Chapitre 9: La récursivité Eléments de contenu A. Introduction @ la récursivité.. 1. Contexte d'utilisation de la récursivité.. 2, Exemple illustratif...s0.cceevnnne . 3, Le déroulement de I'exécution de la fonction récursive. B. Définitions, notations et exemples.....ccccsssisseerssaeissseersnereessee 1. Définition d'un sous-programme récursif. 2, Forme générale et notation d'un sous-programme récursif. 3, Autres exemples. 4, Mécanisme d’exécution d'un sous-programme récursif. C. Correspondance entre un algorithme récursif et un algorithme itératif 109 1, Solution itérative versus solution récursive..... 109 2. Correspondance entre les 2 solutions. Testez vos connaissancesLa récursivité Objectif général Ala fin de ce chapitre vous devez du chapitre + Comprendre les concepts relatifs & la récursivité. Appliquer cette technique pour écrire des algorithmes récursifs en paralléle avec les algorithmes itératifs. Objectifs Comprendre la récursivité et spécifiques du ses différentes formes, chapitre Transformer des — problemes récursifs en des — sous- programmes récu Comprendre les mécanismes d'exécution d'un sous- programme récursif. Transformer des_—_—sous- programmes récursifs en itératifs et vice-versa Donner des solutions récursives pour des problémes Récursivité ; Récursivitéterminale ; Récursivité croisée ; remontée récursive ; descente récursive ; pile =oA. Introduction a la récursivité 1. Contexte d'ut 1 ation de la récursi La récursivité est un mécanisme de programmation qui est utilisé dans le méme objectif que les structures de contrdles itératives. Il s'agit alors d'écrire des sous-programmes récursifs qui font appels a eux méme a la place des boucles afin de résoudre des problémes qui nécessitent une répétition. Cette technique semble étre plus élégante pour le programmeur (mais pas nécessairement plus efficace pour le systéme) surtout dans le cas de problémes qui ont une définition récursive ou qui sont associés a des structures de données récursives. 2. Exemple illustratif Nous allons illustrer dans ce qui suit les principes de la récursivité a travers l'exemple de calcul de la somme de N entiers. Enoncé Soit & écrire une fonction nommée Somme permettant le calcul de la somme de N entiers. La fonction Somme peut étre définie comme suit : Définition 1 : Somme (n) = n + (n-1) + (n-2) +... +2 +140 Définition 2 : Somme (n) = n + Somme (n-1) eT Somme (0) = 0 we Fxemple Somme (4) = 4 + Somme(3) = 4 +3 + Somme (2) 443+ 2+ Somme (1) =443 +241 + somme (0) =44342+140 = 10 Solution Nous allons tout d'abord écrire une version itérative de la fonction Somme, c’est-a-dire en utilisant une boucle. Sachant qu'une fonction (respectivement une procédure) Récursive est une fonction (respectivement une procédure) qui fait appel a elle-méme. En se basant sur la 28me définition de la fonction Somme, nous donnons la version récursive suivante qui permet de calculer la somme de N entiers. oof1 Fowerzow 2 pracr 3 (=O) AL 4 RETOURKER 5 om 5 ? 8 3. Le déroulement de I'exécution de la fonction récur: Pour étre effectivement utilisable, une fonction récursive doit contenir une ou plusieurs conditions d'arrét afin d'éviter le risque d'une récursion infinie. Cette condition est appelée “point terminal” ou "point d'appui” ou “point d'arrét” ou "valeur de base”. Un sous-programme récursif contient au moins un appel au méme sous-programme récursif. Cet appel se fait en changeant les paramétres effectifs d'appel qui doivent se rapprocher de valeurs de base. ’ ; b | Sornme (4) a 7 4+ Somme (3 j : © . 6 Somme (3) e : a + Somme t : e 7 3 Sornme (2) if é 6 7 2+ Som . : u ' 1 Somme(1} r ° 5 i ~ Somme (0 i v : 0 - Remarque Lexécution d'une fonction récursive se déroule en 2 étapes + La descente récursive qui est une suite d'appels récursifs jusqu’a latteinte du point diarrét. + La remontée récursive qui consiste & évaluer les résultats retournés par les appels récursifs et les renvoyer aux niveaux supérieurs des fonctions appelantes. "S888B. Définitions, notations et exemples 1. Définition d'un sous-programme récursif f Définition Un sous-programme est défini de maniére récursive si sa définition fait référence & lui- méme d'une facon directe ou indirecte, I! doit répondre principalement & ces 2 propriétés : + Il doit exister certains arguments appelés que nous avons déjé appelé « points darréts » ou « valeurs de base » pour lesquels le sous-programme s'arréte, sinon elle risque de tourner indéfiniment. + Chaque fois que le sous-programme fait référence & lui-méme, il doit étre plus proche de ses valeurs de base. 2, Forme générale et notation d'un sous-programme récursif On distingue entre 2 types de récursivité : la récursivité simple et la récursivité croisée. La récursivité simple Tous les appels récursifs apparaissent dans le corps du sous-programme récursif. Une procédure récursive simple suit ce modéle : 1 pRocepur: Prec () 2 veeur 3 BT. () ALORS 4 5 saxon 6 [ehutres instructions» 1 8 8 0 eiw La récursivité croisée Dans ce type de récursivité, les appels récursifs sont provoqués par l'exécution d'autres procédures ou fonctions suivant ce modéle : ructions>] 12 pRoceDuRE grec (1) 18 beeun «ST (condition dtarrét>) ALORS Sane e=Exemple Soit les suites mathématiques U et V définies comme suit : Un = 2* Viel +3 sin >=1 Vn = 3* Un-1 +2 sin>= Uo =1 vo =2 Ecrire les fonctions récursives U et V qui permettent de calculer les termes de ces 2 suites. Remarque + XetY sont la liste de paramétres de procédures Prec et Qrec. + F(X) et FCY) sont les fonctions qui permettent de transformer respectivement les parameétres de Prec et Qrec. Une autre distinction est faite entre la récursivité terminale et la récursivité non terminale : + La récursivité terminale : un sous-programme récursif terminal ne contient pas d'autres instructions aprés l'appel récursif. + La récursivité non terminale : un sous-programme récursif non terminal contient d'autres instructions aprés l'appel récursif. 3. Autres exemples & Exemple : Factorielle Ecrire la fonction nommée Fact qui permet de calculer la factorielle d'un entier positif en exploitant les définitions suivantes : Definition 1; nt= 1*2* 3* ...n Définition 2: n= n* (n-1)! La version itérative de la fonction factorielle : 1) Foscrzow 2 3 4 5 6 7 6 9 0 7 11 t "S88La version récursive de la fonction factorielle : FONCTION Pact (DON Nz Entier) Bntie 1 2 av 3 sz ( =0) ALORS 4 RETOURNER 5 srKow 5 1 6 e Exemple_: PGCD Soit & écrire la fonction PGCD qui permet de calculer le plus grand commun diviseur de 2 entiers strictement positifs en utilisant la méthode de soustraction suivante : PGCD (X, ¥) = PGCD (X, Y-X) siX < PGCD (X, ¥) = PGCD (X-Y, Y) siX > ¥ PGCD (X, Y) = X si X: La version récursive de la fonction PGCD ON 26CD (208 x, ¥ + ENtier my 1 (ON PGCD (DON X, ¥ + Entier) + Eatle 2 pesur 3 ‘ANT QUE (X # Y) FAIRE 4 ST 0k < ¥) ALORS 5 ye eK 5 sIxow 7 8 6 0 7 FIN TANT QUE RETOURNER (x) fe Exemple_: Fibonacci Soit & écrire la fonction nommeée FIB qui permet de calculer la suite de Fibonnacci définie comme si FIB (0) = 0 FIB (1) FIB (N) = FIB (N-1) + FIB (N-2) SiN >=2 La version récursive de la fonction FIB Hanne =1 2 peur 3ST (a0) ALORS 4 RETOURKER (0) 5 a8 6 sl w= 1) 7 ‘RETOURNER 8 sam 6 RETOURWER (P18 (N-2) + FIB ( 0 FIN ST i" aw St m0 etK La version itérative de la fonction FIB 1 2 VARIABLE 3 F, Preed, Preeind: Entier 4 5 ALORS 6 7 8 8 10 it 1 2 8 4 15 6 7 FIN 8 FIN st 9 a8 SE 2 ——_RBTOURNER «) aoe 4. Mécanisme d'exécution d'un sous-programme récursif Bien que la récursivité semble étre plus simple et plus élégante pour le programmeur dans la résolution de certains problémes qui sont récursifs par nature ou dans le cas oli ces problémes sont associées a des structures de données récursives, son exécution n'est pas si simple et nécessite le recours une structure de données spécifique nommée pile. La pile est une liste spécifique qui est gérée a travers le protocole LIFO (Last In First Out), Clest-a-dire le dernier élément ajouté est le premier élément traité. L'exécution d'un sous- programme récursif par le systéme suit les phases suivantes: En rencontrant un appel récursif, le systeme réserve lespace pour le résultat et empile (ajoute) dans la pile d'exécution les paramétres, les variables locales et I'adresse de retour. Ala fin de l'appel récursif, le systme dépile (supprime) l'enregistrement, se branche & adresse de retour et y place le résultat. "S88C. Correspondance entre un algorithme récursif et un algorithme itératif 1, Solution itérative versus solution récursive Le choix entre une solution itérative ou récursive dépend de la nature du probléme & résoudre. La récursivité est beaucoup plus facile et compacte dans le cas des problemes récursifs ou les structures de données récursives (liste, arbre, graphe...). Ces avantages ne doivent pas masquer les inconvénients de cette technique tels que le temps d'exécution, lespace mémoire occupée et la difficulté d'estimer la profondeur maximale de la récursivité (Cest 8 dire le nombre maximal d'appels récursifs afin d'atteindre le point d'arrét). Malgré la divergence entre les 2 techniques de programmation, le passage d'un schéma itératif un schéma récursif (la récursifcation) ou d'un schéma récursif @ un schéma itératif (la dérécursification) est généralement possible. 2. Correspondance entre les 2 solutions Nous présentons dans ce qui suit la correspondance entre le schéma itératif et le schéma récursif dans le cas d'une récursivité terminale, Soit P un sous-programme itératif et Prec un sous-programme récursif correspondant. X est la liste de paramétres de la procédure, F(X) est la fonction qui permet de transformer les parameétres lors d'un appel récursif, C(X) est la condition qui permet d'entrer dans la boucle ou faire des appels récursifs et B(X) est le traitement dans le cas de point d'arrét, Schéma récursif 1 2 3 4 5 5 7 6 8 0 Schéma itératif 1 2 3 4 5 6 TANT 1 6 6 0 ni