Fonctions et procédures II : la récursivité

• Les pointeurs II
• Sommaire
• Les Types Abstraits de Données : listes, files, piles…

Le chapitre que vous vous apprêtez à lire est lui aussi compliqué, et pourtant vous n'aurez pas de nouvelle instruction ou de nouveau type composite à connaître.

Nous allons aborder une notion d'algorithmique importante et qui nous servira pour le prochain chapitre : la récursivité. Ceux qui mènent (ou ont mené) des études scientifiques devraient être familiarisés avec un terme similaire : la « récurrence » ! Mais il n'y a pas d'erreur, la récursivité est une notion très proche du raisonnement par récurrence vu au lycée. Pour ceux qui n'ont pas mené ce genre d'étude, n'ayez aucune crainte, nous allons tout prendre à la base, comme toujours.

• Une première définition
• Exemple d'algorithme récursif
• Notre première fonction récursive
• Algorithme de recherche par dichotomie
• Quelques exercices

Une première définition

On dit qu'un programme est récursif si pour parvenir au résultat voulu il se réemploie lui-même. Cela peut s'illustrer par les images suivantes :

Pour réaliser le triangle de sierpinski (premier exemple), on relie les milieux des 3 côtés du grand triangle de manière à former trois triangles "noirs" et un triangle "blanc" à l'envers par rapport aux autres. Puis on reproduit cette opération sur les triangles noirs, et encore, et encore … jusqu'au nombre désiré (Cette figure fait partie de la grande famille des fractales qui ont pour principe de répéter à l'infini sur elles-mêmes la même opération).

Idem pour le nautile, on comprend que pour développer une coquille à 30 alvéoles, le nautile doit avoir développé 29 alvéoles puis en créer seulement une supplémentaire de la même manière qu'il a créé les précédentes. Le nautile répète ainsi sur lui-même à l'infini ou un grand nombre de fois, la même opération : «ajouter une alvéole». Un dernier exemple : l'éponge de Menger, une autre fractale inspirée du carré de Sierpinski. On a ici détaillé les 4 premières étapes :

Est-il besoin de réexpliquer cette fractale ?

Exemple d'algorithme récursif

Imaginons que vous deviez créer un programme affichant un petit bonhomme devant monter N marches d'un escalier et que vous disposez pour cela d'une procédure appelée MonterUneMarche. Il y aura deux façons de procéder. Tout d'abord la manière itérative :

1
2
3
4
5
6
7

PROCÉDURE MonterALaMarche(n) : 

   POUR i ALLANT de 1 à N
    |   MonterUneMarche ; 
   FIN DE BOUCLE

FIN DE PROCÉDURE

Ou alors on emploie une méthode récursive :

1
2
3
4
5
6
7
8

PROCÉDURE MonterALaMarche(n) : 

   SI n > 0
    |   MonterALaMarche(n-1) ; 
    |   MonterUneMarche ; 
   FIN DE SI

FIN DE PROCÉDURE

La méthode récursive est un peu bizarre non ? Une explication s'impose. Si on veut monter 0 marche, c'est facile, il n'y a rien à faire. On a gagné ! En revanche, dans le cas contraire, il faut déjà avoir monté n-1 marches puis en gravir une autre. La procédure MonterMarche fait donc appel à elle-même pour une marche de moins. Prenons un exemple, si l'on souhaite monter 4 marches :

• 4 marches > 0 ! Donc on doit monter déjà 3 marches :
  • 3 marches > 0 ! Donc on doit monter déjà 2 marches :
    • 2 marches > 0 ! Donc on doit monter déjà 1 marche :
      • 1 marche > 0 ! Donc on doit monter déjà 0 marche :
        • 0 marche ! ! ! c'est gagné !
        • Là on sait faire : le résultat renvoyé est que marche = 0.
      • On incrémente marche : le résultat renvoyé est que marche = 1.
    • On incrémente marche : le résultat renvoyé est que marche = 2.
  • On incrémente marche : le résultat renvoyé est que marche = 3.
• On incrémente marche : le résultat renvoyé est que marche = 4.

Ce procédé est un peu plus compliqué à comprendre que la façon itérative (avec les boucles LOOP). Attention ! Comme pour les boucles itératives, il est possible d'engendrer une «boucle récursive infinie» ! Il est donc très important de réfléchir à la condition de terminaison. En récursivité, cette condition est en général le cas trivial, le cas le plus simple qu'il soit, la condition initiale : l'âge 0, la marche n°0, la lettre 'a' ou la case n°1 d'un tableau. Comme pour les boucles itératives, il est parfois utile de dérouler un exemple simple à la main pour être sûr qu'il n'y a pas d'erreur (souvent l'erreur se fait sur le cas initial).

Notre première fonction récursive

Énoncé

Nous allons créer une fonction Produit(a,b) qui effectuera le produit (la multiplication) de deux nombres entiers naturels (c'est-à-dire positifs) a et b. Facile me direz-vous. Sauf que j'ajoute une difficulté : il sera interdit d'utiliser de symbole *. Nous devrons donc implémenter cette fonction uniquement avec des additions et de manière récursive. Cet exemple peut paraître complètement idiot. Toutefois, il vous permettra de réaliser votre premier algorithme récursif et vous verrez que déjà, ce n'est pas de la tarte.

Si vous souhaitez vous lancez seuls, allez-y, je vous y invite. C'est d'ailleurs la meilleure façon de comprendre les difficultés. Sinon, je vous donne quelques indications tout de suite, avant de vous révéler une solution possible.

Indications

Le cas trivial

Tout d'abord quel est le cas trivial, évident ? Autrement dit, quelle sera la condition de terminaison de notre boucle récursive ?

Le cas le plus simple est le cas Produit(a,0) ou Produit(0,b) puisqu'ils renvoient invariablement 0.

Il y a donc deux cas à traiter : si a = 0 ET/OU si b = 0.

Commutativité

Pas d'inquiétude. La propriété de commutativité signifie juste que les nombres d'une multiplication peuvent être «commutés», c'est-à-dire échangés. Autrement dit $a \times b = b \times a$. En effet, que vous écriviez $2 \times 3$ ou $3 \times 2$, cela reviendra au même : le résultat vaudra 6 ! C'est une propriété évidente dont ne bénéficient pas la soustraction ou la division par exemple.

Eh bien pour régler un problème simple : pour effectuer Produit(2,3), c'est-à-dire $2\times 3$, va-t-on faire $2 + 2 + 2$ (c'est-à-dire «3 fois» 2) ou $3 + 3$ (c'est-à-dire «2 fois» 3) ? Le deuxième choix semble plus rapide car il nécessitera moins d'additions et donc moins de récursions (boucles récursives). Il serait donc judicieux de traiter ce cas avant de commencer. Selon que a sera inférieur ou pas à b, on effectuera Produit(a,b) ou Produit(b,a).

Mise en œuvre

Supposons que a soit plus petit que b. Que doit faire Produit(a,b) (hormis le test de terminaison et d'inversion de a et b) ? Prenons un exemple : Produit(3,5). Nous partons d'un résultat temporaire égal à 0 (res = 0).

• 3 > 0. Donc notre résultat temporaire est augmenté de 5 (res = 5) et on fait le produit de 2 par 5 : Produit(2,5).
  • 2 > 0. Donc notre résultat temporaire est augmenté de 5 (res = 10) et on fait le produit de 1 par 5 : Produit(1,5).
    • 1 > 0. Donc notre résultat temporaire est augmenté de 5 (res = 15) et on fait le produit de 0 par 5 : Produit(0,5).
      • 0 ! ! ! Facile. On renvoie le résultat temporaire.

Se pose alors un souci : comment transmettre la valeur temporaire de Res, notre résultat ? La fonction Produit n'a que deux paramètres a et b ! L'idée, est de ne pas surcharger la fonction Produit inutilement avec des paramètres inutiles pour l'utilisateur final. Deux solutions s'offrent à vous : soit vous créez un paramètre Res initialisé à 0 (l'utilisateur n'aura ainsi pas besoin de le renseigner) ; soit vous créez une sous-fonction (Pdt, Mult, Multiplication, appelez-la comme vous voudrez) qui, elle, aura trois paramètres.

Tests et temps processeur

Il est temps de faire un bilan : Produit(a,b) doit tester si a est plus petit que b ou égal car sinon il doit lancer Produit(b,a). Puis il doit tester si a vaut 0, auquel cas il renvoie le résultat, sinon il doit lancer Produit(a-1,b).

Nouveau problème, car en exécutant Produit(a-1,b), notre programme va à nouveau tester si a-1 < b ! Or si a était plus petit que b, a - 1 ne risque pas de devenir plus grand. On effectue donc un test inutile. Ce pourrait être anodin, sauf qu'un test prend du temps au processeur et de la mémoire, et ce temps-processeur et cette mémoire seraient plus utiles pour autre chose. Si nous demandons le résultat de Produit(7418,10965), notre programme devra effectuer 7418 tests inutiles ! Quel gâchis.

Deuxième et dernier bilan :

• Notre fonction Produit(a,b) se contentera de vérifier si a est plus petit ou égal à b. Et c'est tout. Elle passera ensuite le relais à une sous-fonction (que j'appellerais Pdt).
• Notre sous-fonction Pdt sera la vraie fonction récursive. Elle admettra trois paramètres : a, b et res. Le paramètre a devra être impérativement plus petit que b (c'est le travail de la fonction-mère) et res permettra de transmettre la valeur du résultat d'une récursion à l'autre.

Une solution possible

Le code ci-dessous ne constitue en aucun cas la seule et unique solution, mais seulement une solution possible :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

function Produit(a,b : natural) return natural is

   --------------------------
   --     Insérer ici      --
   --  le code source de   --
   --    la fonction Pdt   --
   --------------------------

begin
   if a <= b 
      then return Pdt(a,b,0) ; 
      else return Pdt(b,a,0) ; 
   end if ; 
end Produit ;

Pour plus de clarté, j'ai écrit une fonction Produit non récursive, mais faisant appel à une sous-fonction Pdt dont le code source n'est pas écrit. Cela permet à la fois d'effectuer la disjonction de cas et surtout de fournir une fonction Produit avec seulement deux paramètres. Rassurez-vous, je vous donne tout de même le code de la sous-fonction récursive :

1
2
3
4
5
6
7

function Pdt(a,b,res : natural) return natural is
begin
   if a = 0
      then return res ; 
      else return Pdt(a-1, b, res + b) ; 
   end if ; 
end Pdt ;

Algorithme de recherche par dichotomie

Voici désormais un nouveau programme à réaliser au cours duquel la récursivité va prendre tout son sens. Le principe est d'implémenter un programme Dichotomie() qui recherche un nombre entier dans un tableau préalablement classé par ordre croissant (et sans doublons).

Principe

Par exemple, nous souhaiterions savoir où se trouve le nombre 9 dans le tableau suivant :

Une méthode de bourrin consiste à passer tous les nombres du tableau en revue, de gauche à droite. Dans cet exemple, il faudra donc tester les 6 premiers nombres pour savoir que le 6ème nombre est un 9 ! Comme je vous l'ai dit, 6 tests, c'est une méthode de bourrin. Je vous propose de le faire en 3 étapes seulement avec la méthode par dichotomie (prononcez «dikotomie»).

Ce mot vient du grec ancien et signifie «couper en deux». On retrouve le suffixe «tomie» présent dans les mots appendicectomie (opération consistant à couper l'appendice), mammectomie (opération consistant à couper un sein pour lutter contre le cancer du même nom), lobotomie (opération consistant à couper et retirer une partie du cerveau)… Bref, on va couper notre tableau en deux parties (pas nécessairement égales). Pour mieux comprendre, nous allons dérouler un algorithme par dichotomie avec l'exemple ci-dessus.

_Tout d'abord, on regarde le nombre du «milieu», c'est-à-dire le numéro 5 (opération : ${{1 + 9} \over 2 }= 5$)

Comme 7 est plus petit que 9, on recommence mais seulement avec la partie supérieure du tableau car comme le tableau est ordonné, il ne peut y avoir de 9 avant !

On prend à nouveau le nombre du «milieu». L'opération ${{6+9} \over 2}$ donne 7,5 ! Donc nous allons considérer que le nombre du «milieu» est le n°7 (je sais, ce n'est pas mathématiquement rigoureux, mais c'est bien pour cela que j'utilise des guillemets depuis le début).

Le nombre obtenu (15) est plus grand que 9, on recommence donc avec la partie inférieure du tableau.

Le nombre du «milieu» est le n°6 (logique) et il vaut 9. C'est gagné ! Notre résultat est que «le 9 est à la 6ème case».

_

Avec cet algorithme, je n'ai testé que la 5ème, la 7ème et la 6ème valeur du tableau, soit seulement 3 tests au lieu de 6 pour la méthode «bourrin» (on parle de force brute). Et cet écart peut très vite s'accroître notamment pour rechercher de grandes valeurs dans un grand tableau. Nous verrons dans le chapitre sur la complexité des algorithmes que le premier algorithme a une complexité en $O(n)$, tandis que le second a une complexité en $O(log(n))$. Oui, je sais, pour vous c'est du Chinois. Nous expliquerons cela plus tard, retenez seulement que cela signifie que pour un petit tableau, l'intérêt de la dichotomie est discutable ; en revanche pour un grand ou très grand tableau, il n'y a pas photo sur la plus grande efficacité de la dichotomie.

Mise en œuvre

Nous allons désormais implémenter notre programme Dichotomie(). Toutefois, vous aurez remarqué qu'il utilise des tableaux de tailles différentes. Nous avons donc un souci car nous ne savons déclarer que des tableaux de taille fixe. Deux solutions sont possibles :

• Regarder le chapitre de la partie 4 sur la généricité pour pouvoir faire des tableaux dont on ne connaît pas préalablement la taille. Le problème, c'est que l'on risque de vite se mélanger les pinceaux, d'autant plus que ce chapitre est dans une partie encore plus dure.
• Faire en sorte que notre programme manipule un tableau T de taille fixe mais aussi deux variables Min et Max qui indiqueront la «plage» du tableau qui nous intéresse («cherche dans le tableau T entre l'indice Min et l'indice Max»). Nous retiendrons pour l'instant, vous vous en doutez, cette seconde solution. Toutefois, il sera judicieux de reprendre ce programme après avoir vu la généricité.

Autre question : que donne la division 15/2 en Ada ? Réponse :

1

Reponse :     7_

Puisque nous divisons deux integer, Ada nous renvoie également un integer. Or vous savez bien que cette division ne «tombe pas juste» et qu'elle devrait donner 7,5 ! Mais Ada doit faire un choix : soit la valeur approchée à l'unité près par excès (8) soit la valeur approchée à l'unité près par défaut (7). Le choix a été fait de renvoyer la valeur par défaut car elle correspond à la partie entière du nombre décimal. Toutefois, si vous vouliez savoir durant la programmation de cet algorithme, si un nombre est pair ou impair, je vous rappelle qu'il existe l'opération MOD !

Exemple : 15 mod 2 = 1 (Donc 15 est impair) ; 18 mod 2 = 0 (Donc 18 est pair).

Dernier problème à régler : que faire s'il n'y a pas de 9 ? Renvoyer une valeur particulière ? Ce n'est pas la meilleure idée. L'utilisateur final n'est pas sensé le savoir. Renvoyer l'indice de la valeur la plus proche ? Pourquoi pas mais si l'utilisateur ne connaît pas cette nuance, cela peut poser problème. Le mieux serait de renvoyer deux résultats : un booléen Existe indiquant si la valeur existe ou non dans le tableau et une variable Indice indiquant la valeur trouvée (seulement si Existe vaut true).

Dès lors, plusieurs solutions s'offrent à vous : vous pouvez créer un type structuré (avec RECORD) pour renvoyer deux résultats en même temps. Ou vous pouvez créer une procédure avec deux paramètres en mode OUT ou encore utiliser un pointeur sur booléen comme paramètre à votre fonction pour savoir savoir si le résultat existe. A vous de choisir.

Solution

Voici une solution possible pour le programme Dichotomie() :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Procedure Dichotomie is

type T_Tableau is array(1..50) of integer ;         --à vous de choisir la taille du tableau
type T_Ptr_Bool is access boolean ; 

   ----------------------------------
   --   Insérer ici le code source --
   --   de la fonction récursive   --
   ----------------------------------

T : T_Tableau ; 
Existe : T_Ptr_Bool ; 
Indice : integer ; 

begin

Init(T) ;                                           --à vous d'initialiser ce tableau
Existe := new boolean ;                             --création et initialisation du pointeur
Existe.all := false ; 
Indice := Dicho(T, 13, Existe, T'first, T'last) ;   --on cherche le nombre 13 dans le tableau T

if Existe.all
   then put("Le nombre 13 est à l'indice numero") ; 
        put(Indice) ; 
   else put("Le nombre 13 n'est pas présent dans le tableau") ; 
end if ;
end Dichotomie ;

Dans le programme ci-dessus, on recherche le nombre 13 dans un tableau de 50 cases. La procédure d'initialisation n'est pas écrite, je vous laisse le faire (pensez que le tableau doit être ordonné !). Voici maintenant le code de la fonction Dicho() :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

function Dicho(T : T_Tableau ; 
               N : integer ; 
               Existe : T_Ptr_Bool ; 
               Min, Max : integer) return integer is

   Milieu : integer ; 

begin

   Milieu := (Min+Max) / 2 ;
 
   if T(Milieu) = N                  --Cas où on trouve le nombre N cherché
      then Existe.all := true ; 
           return Milieu ; 

   elsif Min = Max                   --Cas où l'on n'a pas trouvé N et où on ne peut plus continuer
      then Existe.all := false ;     --On indique que N n'existe pas et on renvoie 0. 
           return 0 ; 

   elsif T(Milieu) > N               --Cas où on peut continuer avec un sous-tableau
      then return Dicho(T,N,Existe,Min,Milieu-1) ; 
      else return Dicho(T,N,Existe,Milieu+1,Max) ; 
   end if ; 

end Dicho ;

Nous avons cette fois réalisé un programme où l'utilisation de la récursivité est vraiment pertinente. À quoi reconnaît-on qu'un programme pourrait être traité de manière récursive ? Tout d'abord il faut avoir besoin de répéter certaines actions. La question est plutôt : pourquoi choisir un algorithme récursif plutôt que itératif ? La réponse est en grande partie dans la définition même de la récursivité. Il faut se trouver face à un problème qui ne se résolve qu'en réemployant les mêmes procédés sur un même objet. Les algorithmes récursifs nécessitent généralement de disjoindre deux cas : le cas simple, trivial et le cas complexe. Ce dernier peut être lui-même subdivisé en plusieurs autres cas (a<b et="" a="">b ; n pair et n impair…).</b>

Quelques exercices

Exercice 1

Énoncé

Rédigez une fonction récursive Factorielle( ) qui calcule… la factorielle du nombre donné en argument. Pour exemple, la factorielle de 7 est donnée ainsi : $7 ! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$. Ainsi, votre fonction Factorielle(7) renverra 5040.

Solution

1
2
3
4
5
6
7

function factorielle(n : integer) return integer is
begin
   if n>0
      then return n*factorielle(n-1) ;
      else return 1 ; 
   end if ;
end factorielle ;

Exercice 2

Énoncé

Rédigez une fonction récursive Puissance(a,n) qui calcule la puissance n du nombre a (c'est-à-dire $a^n$), mais seulement en utilisant des multiplications.

Solution

1
2
3
4
5
6
7

function puissance(a,n : integer) return integer is
begin
   if n > 0
      then return a*puissance(a,n-1) ; 
      else return 1 ; 
   end if ; 
end puissance ;

Exercice 3

Énoncé

Rédigez des fonction récursives Affichage( ) et Minimum( ). Chacune devra parcourir un tableau, soit pour l'afficher soit pour indiquer l'indice du plus petit élément du tableau.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

type T_Tableau is array(1..10) of integer ;

Procedure Affichage(T : T_Tableau) is
   procedure Afg(T : T_Tableau ; dbt : integer) is
   begin
      put(T(dbt),1) ; put(" ; ") ;
      if dbt < T'last
         then Afg(T,dbt+1) ; 
      end if ; 
   end Afg ; 
begin
   Afg(T,T'first) ; 
end Affichage ; 
   
function Minimum(T:T_Tableau) return integer is
   function minimum(T:T_Tableau ; rang, res, min : integer) return integer is
         --rang est l'indice que l'on va tester
         --res est le résultat temporaire, l'emplacement du minimum trouvé jusque là
         --min est le minimum trouvé jusque là
      min2 : integer ; 
      res2 : integer ; 
   begin
      if T(rang) < min
         then min2 := T(rang) ;
              res2 := rang ; 
         else min2 := min ; 
              res2 := res ; 
      end if ; 
      if rang = T'last
         then return res2 ; 
         else return minimum(T,rang+1,res2,min2) ; 
      end if ; 
   end minimum ; 
begin
   return minimum(T,T'first+1,T'first,T(T'first)) ;
end Minimum ;

Exercice 4

Énoncé

Rédigez une fonction récursive Effectif(T,x) qui parcourt un tableau T à la recherche du nombre d'apparition de l'élément x. Ce nombre d'apparition est appelé effectif. En le divisant par le nombre total d'élément dans le tableau, on obtient la fréquence (exprimée en pourcentages si vous la multipliez par 100). Cela vous permettra ainsi de rédiger une seconde fonction appelée Fréquence(T,x). Le tableau T pourra contenir ce que vous souhaitez, il peut même s'agir d'un string.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

function effectif(T: T_Tableau ; x : integer) return integer is
   function effectif(T:T_Tableau ; x : integer ; rang, eff : integer) return integer is
      eff2 : integer ; 
   begin
      if T(rang) = x
         then eff2 := eff +1 ; 
         else eff2 := eff ;
      end if ; 
      if rang=T'last
         then return eff2 ; 
         else return effectif(T,x,rang+1,eff2) ; 
      end if ; 
   end effectif ; 
begin
   return effectif(T,x,T'first,0) ; 
end effectif ; 


function frequence(T : T_Tableau ; x : integer) return float is
begin
   return float(effectif(T,x))/float(T'length)*100.0 ;
end frequence ;

Bien, nous avons désormais terminé ce chapitre sur la récursivité. Cette notion va nous être utile au prochain chapitre puisque nous allons aborder un nouveau type composite : les types abstraits de données. Ce chapitre fera appel aux pointeurs, aux types structurés et à la récursivité. Ce sera le dernier chapitre théorique de cette partie et probablement le plus compliqué, donc si vous avez encore des difficultés avec l'une de ces trois notions, je vous invite à relire les chapitres précédents et à vous entraîner car les listes sont des objets un peu plus compliqués à manipuler.

J'espère que ce chapitre vous aura permis d'avoir une idée assez précise de ce qu'est la récursivité et de l'intérêt qu'elle peut représenter en algorithmique. Pour disposer d'un second point de vue, je vous conseille également la lecture du tutoriel de bluestorm disponible sur le site du zéro en cliquant ici. Toutefois, s'il est plus complet concernant la notion de récursivité, ce tutoriel n'est pas rédigé en Ada, vous devrez donc vous contenter de ses explications.

En résumé :

• Les boucles récursives permettent, comme les boucles itératives, de répéter une tâche. Il suffit pour cela qu'une procédure ou une fonction s'appelle elle-même.
• Un programme récursif doit envisager plusieurs cas et notamment le cas trivial qui mettra fin à la boucle récursive. Une fois ce cas évident établi, vous devez réfléchir à l'opération à effectuer pour passer à l'étape supérieure.
• Les algorithmes récursifs nécessitent plus d'entraînement et de réflexion que les algorithmes itératifs. Nous verrons au prochain chapitre que certaines structures s'adaptent mieux à ce type de raisonnement. C'est pourquoi vous devez malgré tout vous entraîner à la récursivité, malgré les difficultés qu'elle peut présenter.

• Les pointeurs II
• Sommaire
• Les Types Abstraits de Données : listes, files, piles…