Chapitre 5. Récursivité et listesmathinfo.univ-reims.fr/IMG/pdf/chap5-2.pdf · Algorithmique et programmation C Chap. 5 – Récursivité et listes Utilisation des structures et

Algorithmique et programmation C Chap. 5 – Récursivité et listes

Chapitre 5. Récursivité et listes

La récursivité :– permet une écriture plus claire des algorithmes ;– les algorithmes sont généralement plus courts ;– il est plus facile de prouver la terminaison et la correction ;– le calcul de la complexité est simplifié.

Les listes :– c’est un type de données naturellement récursif ;– la gestion de la mémoire est généralement dynamique ;– très utiles pour représenter des problèmes irréguliers.

M. KRAJECKI 1 DESS IAS – Année 2003-2004


1. La récursivité

Définition 1 (Récursivité) Une fonction (ou une procédure)�

est diterécursive, si pour la définir (écrire son algorithme), au moins une référence àelle même (un appel à

�) est utilisée.

Par exemple, il est possible de définir �� ainsi :

� �� et ��

int fact(int n) {

if (n==0) return 1 ;

else return n*fact(n-1) ;

}



Récursivité terminale

Un autre exemple, la définition récursive du pgcd :

int pgcd(int a, int b) {

if (a==b) return a ;

else if (a>b) return pgcd(a-b,b) ;

else return pgcd(a, b-a) ;

}

Vous pouvez remarquer que dans les deux exemples précédents, l’appelrécursif est la dernière instruction exécutée. On parle dans ce cas de

récursivité terminale.



Elimination de la récursivité terminale

Il est facile de rendre une fonction récursive terminale en une fonction nonrécursive.

Il suffit de simuler la récursivité par une boucle tant que.

La négation du test d’arrêt de la récursivité étant utilisée pour le test de laboucle tant que.

Voici par exemple, la fonction itérative fact :

int fact(int n) {

int f = 1;

while (n!=0) {

f=f*n ; n -= 1 ;}

return f ;}



Recherche dichotomique

Voici un autre exemple de récursivité terminale.

int dicho(int t[], int binf, int bsup, int v) {

if (binf>bsup) return -1 ;

else {

int p = (binf+bsup)/2 ;

if (t[p]==v) return p ;

else if (t[p]>v) return dicho(t, binf, p-1, v);

else return dicho(t, p+1, sup, v);

}

}



Récursivité non terminale et croisée

Quand, dans la définition d’une fonction récursive, l’appel récursif ne termine

pas la fonction, on parle de récursivité non terminale.

La suppression de la récursivité non terminale est plus délicate. Une pile estalors nécessaire pour mémoriser l’état de la mémoire avant l’appel récursif.

Quand une fonction A est définie à l’aide du fonction B, elle même définie à

l’aide de A, on parle de récursivité croisée.

La suppression de la récursivité croisée, comme pour la récursivité nonterminale, est généralement délicate.



2. Les listes simplement et doublement chainées

Définition 2 (Liste) Une liste est une succession de valeurs d’unmême type pour lesquelles un accès direct n’est pas fréquent.

Le type liste peut être défini récursivement :

�� où

��et

��

Remarque : si nous acceptons cette définition,�� !��#"$�!�%�&�%��(')�

devraitêtre notée par

��)�!�*��#"$�*�+�%�&�%�*��(',�*��-�.�%�&�/�-�.



Fonctions de base

Les actions de bases sur les listes sont définies par les 5 fonctionssuivantes :

1. Vide : 0 ��1 �32542. Tête : 0 ��1 � ��6�� 8792:13. Queue : 0 ��1 � ��6�� 879250 ��1 �4. ConsVide : 2;6�� 875. Cons : 1 �<0 ��1 �=2>0 ��1 �

Il est possible de montrer que tous les traitements sur les listes linéairespeuvent être écrits à l’aide de ces 5 primitives. Cependant, pour desproblèmes d’efficacité, il est parfois nécessaire d’étendre cet ensemble deprimitives.



Comparaison entre listes et tableaux

La représentation des listes par chaînages est classique. Elle permet unegestion dynamique de la mémoire et de faciliter l’insertion et la suppressionde valeurs.

1 2 3 4

l:

insertion / suppression mémoire accès aléatoire

Tables mauvais (décalage) a priori mauvais bon

Listes rapide (chaînage) a priori bon mauvais



Représentation par chaînage

Afin de représenter les listes par chaînages, nous allons définir la notion decellule. Une cellule comporte deux informations :– une valeur de la liste ;– un accès à la prochaine cellule de la liste ;Une liste est alors définie par l’accès à la première cellule qui la compose.

v1 v2 vn

l:

la première cellule une valeur l’accès à la prochaine cellule

l’accès à la première cellule



Utilisation des structures et des pointeurs

En C, il existe un moyen de regrouper plusieurs valeurs dans unenregistrement (un bloc de mémoire contigüe). Voici un cours exemple quiregroupe deux entiers dans une structure :

struct deuxentiers {

int a ;

int b ;

};

main() {

struct deuxentiers v;

v.a = 5 ; v.b = 10;

printf("%d, %d\n", v.a, v.b);

}



Utilisation des structures et des pointeurs

Pour représenter une cellule en C, l’utilisation de structures est conseillée.

Le deuxième champs de la structure (l’accès à la prochaine cellule) seradéfini comme un pointeur sur une cellule. Voici la définition en C d’unecellule pour une liste de caractères :

struct cellule {

char valeur ;

struct cellule *suivant ;

} ;

De même, une liste sera définie comme un pointeur sur une cellule...



Exemple : définition d’une liste d’entiers

#include <stdlib.h>

#define VRAI !0

#define FAUX 0

#define BOOLEEN int

/* le type liste d’entiers */

typedef struct element {

int valeur ;

struct element *suivant ;

} element, * Liste ;




/* Les fonctions de base */

BOOLEEN Vide(Liste L) {

return (L==NULL) ;

}

int Tete(Liste L) {

return L->valeur ;

}

Liste ConsVide() {

return NULL ;

}




Liste Queue(Liste L) {

return L->suivant ;

}

Liste Cons(int V, Liste L) {

Liste tmp ;

tmp = (Liste) malloc(sizeof(element)) ;

tmp->valeur=V;

tmp->suivant=L;

return tmp ;

}




Liste Saisie() {

int v=0; Liste l;

l=ConsVide();

printf("Valeur (-1 pour terminer) ?");

scanf("%d",&v);

while(v>=0) {

l=Cons(v,l);

printf("Valeur (-1 pour terminer) ?");

scanf("%d",&v);

}

return l;

}




void Affiche(Liste L) {

if (Vide(L)) printf("()");

else {

printf("( %d, ", Tete(L));

Affiche(Queue(L)); printf(")");

}

}

/* un petit programme principal */

main() {

Liste maliste;

maliste=Saisie();

Affiche(maliste);

}



3. Représentation de polynômes creux par des listes

1. Représentation à l’aide de tableaux :

0 1 2 3 4

0 0 0 14 P(x) = x²+4

Pb :– nécessité de connaître la taille du polynôme le plus grand

– représentation à trou (par exemple� ��

��).

2. Utilisation de listes :

4 0 1 2

coef coef degrédegré

P(x) = x²+4

P



Définition du type + fonctions de base

Une cellule contiendra 3 informations : le degré du monome, le coefficient

associé et un lien sur le monome suivant.

2 fonctions en création :– Creation() : Polynome (création d’un nouveau polynôme) ;– ConsPoly(d : entier, c : reel, p : Polynome) :

Polynome.

4 fonctions de consultation :– PolyVide(p : Polynome) : Booleen ;– Coef(p : Polynome) : reel ;

– Degre(p : Polynome) : entier ;– Suivant(p : Polynome) : Polynome ;



Manipulation des polynômes

1. Quelques fonctions simples :– affichage et saisie d’un polynôme : attention à l’ordre et aux doublons ;– longueur, evaluation et dérivation.

2. Tri d’un polynôme :– tri par insertion ;

– comment écrire efficacement une fonction d’insertion ?

3. Addition et multiplication de 2 polynômes triés :– algorithmes (un peu) plus complexes ;

– le tri est important : il simplifie le travail.



Définition du type

#include <stdlib.h>

#include <math.h>

#define VRAI !0

#define FAUX 0

#define BOOLEEN unsigned char

typedef struct poly_nonvide {

float coef ;

int degre ;

struct poly_nonvide *suivant ;

} poly_nonvide, *Polynome;



Les fonctions de base

BOOLEEN PolyVide(Polynome P){

return (P==NULL) ;

}

float Coef(Polynome P) {

return P->coef ;

}

int Degre(Polynome P) {

return P->degre ;

}

Polynome Suivant(Polynome P){

return P->suivant ;

}



Les fonctions de base

Polynome Creation(){

return NULL ;

}

Polynome ConsPoly(int d, float c, Polynome P){

Polynome premier ;

premier = (Polynome) malloc(sizeof(poly_nonvide)) ;

premier->degre=d;

premier->coef=c;

premier->suivant=P;

return premier ;

}



Affichage d’un polynôme

void Affiche(Polynome P){

if (!PolyVide(P)){

if (!PolyVide(Suivant(P))){

if (Coef(Suivant(P))>0)

printf("%f * x^%d + ", Coef(P), Degre(P));

else

printf("%f * x^%d ", Coef(P), Degre(P));

Affiche(Suivant(P));

}

else /* c’est le dernier monome */

printf("%f * x^%d.\n", Coef(P), Degre(P));

}

}



Saisie d’un polynôme

Polynome Saisie() {

int d; float c;

printf("Degré du monome à ajouter

(-1 pour terminer) ?");

scanf("%d",&d);

if(d>=0) {

printf("Coef du monome à ajouter ?");

scanf("%f",&c);

return ConsPoly(d,c,Saisie());

}

else return Creation();

}



Évaluation et dérivation d’un polynôme

Polynome Derive(Polynome P) {

if (PolyVide(P)) return Creation();

else if (Degre(P)>0)

return ConsPoly(Degre(P)-1, Degre(P)*Coef(P),

Derive(Suivant(P)));

else return Derive(Suivant(P));

}

float Evalue(float x, Polynome P) {

if (PolyVide(P)) return 0 ;

else return (Coef(P) * pow(x, Degre(P))

+ Evalue (x, Suivant(P)));

}



Tri d’un polynôme

Polynome InsertionTriee(int d, float c, Polynome P){

if (PolyVide(P))

return ConsPoly(d,c,Creation());

else if (Degre(P)<d)

return ConsPoly(d,c,P);

else return ConsPoly(Degre(P), Coef(P),

InsertionTriee(d,c,Suivant(P)));

}

Polynome TriPoly(Polynome P){

if (PolyVide(P)) return Creation();

else return InsertionTriee(Degre(P), Coef(P),

TriPoly(Suivant(P)));

}



Addition de deux polynômes

Polynome Addition(Polynome P1, Polynome P2) {

if (PolyVide(P1)) return P2 ;

else if (PolyVide(P2)) return P1 ;

else if (Degre(P1) > Degre(P2))

return ConsPoly(Degre(P1), Coef(P1),

Addition(Suivant(P1), P2));

else if (Degre(P2) > Degre(P1))

return ConsPoly(Degre(P2), Coef(P2),

Addition(P1, Suivant(P2)));

else if (Coef(P1)+Coef(P2)!=0)

return ConsPoly(Degre(P1), Coef(P1)+Coef(P2),

Addition(Suivant(P1),Suivant(P2)));

else return Addition(Suivant(P1),Suivant(P2));}



Multiplication de deux polynômes

Polynome Multi(int d, float c, Polynome P) {

if (c==0) return Creation();

else if (PolyVide(P)) return Creation();

else return ConsPoly(d+Degre(P), c*Coef(P),

Multi(d,c,Suivant(P)));

}

Polynome Multiplication (Polynome P1, Polynome P2) {

if (PolyVide(P1)) return Creation();

else

return Addition(Multi(Degre(P1), Coef(P1), P2),

Multiplication(Suivant(P1),P2));

}



Un petit programme principal

main(){

Polynome p1=Creation(),p2=Creation();

int choix=1; float x;

while(choix!=0) {

printf("1. Saisie du polynôme 1.\n");

printf("2. Saisie du polynôme 2.\n");

printf("3. Evaluation du polynôme 1.\n");

printf("4. Addition des 2 polynômes.\n");

printf("5. Multiplication des 2 polynômes.\n");

printf("Votre choix (0 pour quitter) ? ");

scanf("%d",&choix);



Un petit programme principal

switch(choix) {

case 1: {p1=Saisie(); Affiche(p1); break;}

case 2: {p2=Saisie(); Affiche(p2); break;}

case 3: {

printf("x="); scanf("%f",&x);

printf("P1(%f)=%f\n",x,Evalue(x,p1));

break;}

case 4: {Affiche(Addition(p1,p2));break;}

case 5: {Affiche(Multiplication(p1,p2));break;}

}

}

}


Documents

Chapitre 5. Récursivité et listesmathinfo.univ-reims.fr/IMG/pdf/chap5-2.pdf · Algorithmique et programmation C Chap. 5 – Récursivité et listes Utilisation des structures et