progII 1

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 47

Programmation II

Module: M1 - LFSMI - S4

Prof. R. HANNANE
[email protected]

Faculté des Sciences Semlalia, Marrakech


Université Cadi Ayyad

Prof. R. HANNANE (FSSM) Programmation II 1 / 47


Programmation II
Objectif du cours

I L’objectif principal de ce module est de vous permettre de compléter vos acquis durant le
module ”programmation I” et d’acquérir de nouvelles connaissances dans le cadre de la
programmation avancée en langage C.
I Suite à ce cours, vous devrez être aptes à :
Développer de programmes modulaires (structurés) et réutilisable (notion de fonctions, etc.)
Assurer une gestion dynamique des données en mémoire (allocation dynamique, pointeurs,
etc.)
Assurer un stockage et gestion optimale des données sur disque dur (fichier, types composés,
etc.)
Faire des programmes maintenables et réutilisables (compilation séparée, création de librairies,
etc.)

Pre-requis
I M1 : Programmation I (S2)
I M2 : Algorithme II (S2)

Évaluation
I Contrôle final * 2 1
3
+ Contrôle continue (TP/TD rendus + assiduité) * 3

Prof. R. HANNANE (FSSM) Programmation II 2 / 47


Programmation II
Le Plan du cours
1 Les Fonctions en C
2 Les Pointeurs
3 Gestion dynamique de la mémoire
4 Les Chaı̂ne de caractères
5 Les types composées
6 Les Fichiers
7 Programmation modulaire

Prof. R. HANNANE (FSSM) Programmation II 3 / 47


Les Fonctions en C

Les Fonctions en C

Prof. R. HANNANE (FSSM) Programmation II 4 / 47


Les Fonctions en C

Notion de Fonction en C
En mathématiques, une fonction est défini par un nom qui
prend des arguments ou paramétres, et rend un résultat.
⇒ Il en est presque de même en C. Une fonction est une suite
d’instructions regroupées sous un nom et qui peut
prendre ou pas des arguments et rend aussi un résultat.
Ce pendant on doit spécifier le type des paramétres et
aussi du résultat.
En C, la fonction pourra prendre des aspects différents,
comme:
I La valeur d’une fonction pourra ne pas être utilisée
I Une fonction pourra ne fournir aucune valeur
I Une fonction pourra fournir un résultat non scalaire
I Une fonction pourra modifier les valeurs de certains de ses
arguments
Prof. R. HANNANE (FSSM) Programmation II 5 / 47
Les Fonctions en C

Notion de Fonction en C

Définition d’une fonction

Déclaration d’une fonction

L’appel d’une fonction

Prof. R. HANNANE (FSSM) Programmation II 6 / 47


Les Fonctions en C

Définition d’une fonction en C


Une fonction se défine à l’extérieur de toute autre fonction y
compris le programme main()
La définition d’une fonction possède une structure voisine de la
fonction main, à savoir un en-tête et un corps délimité par des
accolades ({ et } )

Définition d’une fonction


/∗En−t ê t e g é né r a l e de l a f o n c t i o n ∗/
t y p e r e t o u r nom Fonction ( type arg1 , type arg2 , ...)
{ /∗ Le c o r p s de l a f o n c t i o n ∗/

instruction1 ;
instruction2 ;
...;
return r e s u l t a t ;
}

Prof. R. HANNANE (FSSM) Programmation II 7 / 47


Les Fonctions en C

Définition d’une fonction en C

L’en-tête est plus élaboré que celui de la fonction main puisque,


outre le nom de la fonction (exemple de fonction fplus), on y
trouve une liste d’arguments (type+nom ), ainsi que le type
de la valeur (résultat) qui sera fournie par la fonction

Exemple d’en-tête de fonction


int fplus ( int x , int y)
| | | |
t y p e de l a nom de 1 er 2eme
” v a l e u r de ” la fonction a r g u m en t ar g u m e nt
” retour ” ( type i n t ) ( type i n t )
/ ”resultat”

Prof. R. HANNANE (FSSM) Programmation II 8 / 47


Les Fonctions en C

Définition d’une fonction en C


Formes d’en-tête de fonctions

Les différentes formes d’en-tête de fonctions suivant ces


cas:
1 Fonction sans résultat et sans arguments
void nom fonction(void)

2 Fonction sans résultat et avec arguments


void nom fonction(liste arguments)

3 Fonction avec résultat et sans arguments


type retour nom fonction(void)

4 Fonction avec résultat et avec arguments


type retour nom fonction(liste arguments)

Prof. R. HANNANE (FSSM) Programmation II 9 / 47


Les Fonctions en C

Définition d’une fonction en C


Formes d’en-tête de fonctions
1 Fonction sans résultat et sans arguments
void nom fonction(void)
Exemple: Fonction sans résultat et sans arguments
/* D é finition de la fonction erreur */
void erreur ( void ) /* ou bien void erreur () */
{
printf ( " *** erreur ***\ n " ); /* Attention , absence de return ici */
}

2 Fonction sans résultat et avec arguments


void nom fonction(liste arguments)
Exemple: Fonction sans résultat et avec arguments
/∗Dé f i n i t i o n de l a f o n c t i o n a f f i c h e c a r r e s ∗/
void a f f i c h e c a r r e s ( i n t d ){
p r i n t f ( ”%d a p o u r c a r r é %d\n” , d , d∗d ) ;
/∗ A t t e n t i o n , a b s e n c e de r e t u r n i c i ∗/
}
Prof. R. HANNANE (FSSM) Programmation II 10 / 47
Les Fonctions en C

Définition d’une fonction en C


Formes d’en-tête de fonctions

3 Fonction avec résultat et sans arguments


type retour nom fonction(void)
Exemple: Fonction avec résultat et sans arguments
/* D é finition de la fonction compte .
Le terme void ici est facultatif */
int compte ( void ){
static int i ;
++ i ;
return i ; /* Attention , pr é sence de return ici */
}
4 Fonction avec résultat et avec arguments
type retour nom fonction(liste arguments)
Exemple: Fonction avec résultat et avec arguments
/* D é finition de la fonction fplus */
int fplus ( int a , int b ){
return ( a + b ); /* Attention , pr é sence de return ici */
}
Prof. R. HANNANE (FSSM) Programmation II 11 / 47
Les Fonctions en C

Déclaration d’une fonction


Une fonction se déclare à l’intérieur des déclarations de toute
fonction l’utilisant
/∗∗ ∗∗∗ l e programme p r i n c i p a l ( f o n c t i o n main ) ∗∗∗∗ ∗/
i n t main ( ) {
int f p l u s ( int , int ) ; /∗Dé c l a r a t i o n de l a f o n c t i o n f p l u s ∗/
...
return 0;
}
void fct1 ( ) { . . . }

Mais il est également possible d’utiliser des déclarations


globales, en les faisant apparaı̂tre avant la définition de la
première fonction.
/∗ Dé c l a r a t i o n g l o b a l e de l a f o n c t i o n f p l u s ∗/
int f p l u s ( int , int ) ;
/∗∗ ∗∗∗ l e programme p r i n c i p a l ( f o n c t i o n main ) ∗∗∗∗ ∗/
i n t main ( ) { . . . r e t u r n 0 ; }
v o i d f c t 1 ( ) { . . . } /∗ I c i , f p l u s e s t c o n n u e à
l a f o i s de main e t de f c t 1 ∗/
Prof. R. HANNANE (FSSM) Programmation II 12 / 47
Les Fonctions en C

Déclaration d’une fonction

Remarque:
Une fonction ne peut être déclarée plus d’une fois dans un
programme

La déclaration d’une fonction n’est pas obligatoire

Une fonction doit être déclarée avant d’être utilisée

La déclaration d’une fonction peut être plus ou moins détaillée

Prof. R. HANNANE (FSSM) Programmation II 13 / 47


Les Fonctions en C

Déclaration d’une fonction

Il est recommandé d’employer toujours la forme la plus


complète possible qu’on nomme prototype (qui précise en plus
le type de ses arguments)
Exemple prototype
int compte ( void );
int fplus ( int , int );

⇒ Pourquoi??

Prof. R. HANNANE (FSSM) Programmation II 14 / 47


Les Fonctions en C

Déclaration d’une fonction

⇒ Le prototype peut être utilisé par le compilateur de deux façons


complètement différentes:

1 Si la définition de la fonction se trouve dans le même fichier


source (que ce soit avant ou après la déclaration), il s’assure
que les arguments muets ont bien le type défini dans le
prototype.
Dans le cas contraire, il signale une erreur.

Prof. R. HANNANE (FSSM) Programmation II 15 / 47


Les Fonctions en C

Déclaration d’une fonction

2 Lorsqu’il rencontre un appel de la fonction, il met en place


d’éventuelles conversions des valeurs des arguments
effectifs dans le type indiqué dans le prototype.
f l o a t a =2.0 , b =1.5;
f p l u s ( a ∗3 , b+2)

sera traduit par :


L’évaluation de la valeur de l’expression a*3 (en float) et sa
conversion en int,

L’évaluation de la valeur de l’expression b+2 (en float) et sa


conversion en int

Prof. R. HANNANE (FSSM) Programmation II 16 / 47


Les Fonctions en C

L’appel d’une fonction

Une fonction est appelée lorsque cela est nécessaire

L’appel d’une fonction dépend de son type


1 Fonction sans résultat et sans arguments
⇒ nom_fonction ();
Exemple appel de fonction sans résultat et sans arguments
erreur () ; /* Appel de la fonction erreur */

2 Fonction sans résultat et avec arguments


⇒ nom_fonction ( arg1 , arg2 ,...);
Exemple appel de fonction sans résultat et avec arguments
affi che_carr es (5); /* Appel de la fonction affiche_ carres */

Prof. R. HANNANE (FSSM) Programmation II 17 / 47


Les Fonctions en C

L’appel d’une fonction

3 Fonction avec résultat et sans arguments


⇒ var1 = nom_fonction ();
var1 = var2 * nom_fonction ();

⇒ printf ( nom_fonction ());

Exemple appel de fonction avec résultat et sans arguments


int c ;
/* Appel de la fonction compte soit : */
c = compte () ; /* ou bien */
int m =3* compte (); /* ou bien */
printf ( compte ());

Prof. R. HANNANE (FSSM) Programmation II 18 / 47


Les Fonctions en C

L’appel d’une fonction

4 Fonction avec résultat et avec arguments


⇒ var1 = nom_fonction ( arg1 , arg2 ,...);
var1 = var2 * nom_fonction ( arg1 , arg2 ,...);

⇒ printf ( nom_fonction ( arg1 , arg2 ,...));

Exemple appel de fonction avec résultat et avec arguments


int c , a =2 , b =4;
/* Appel de la fonction fplus soit : */
c = fplus (a , b ) ; /* ou bien */
int m =3* fplus (a , b ); /* ou bien */
printf ( " La somme de % d et % d est : % d \ n " ,a ,b , fplus (a , b ));

Prof. R. HANNANE (FSSM) Programmation II 19 / 47


Les Fonctions en C

L’appel d’une fonction

Dans le cas général, une fonction est appelée ainsi:


I Si la fonction renvoie un résultat d’un type t,
alors, on affecte ce résultat à une variable var de type t par
l’intermédiaire d’une instruction de la forme: var = f (x);

I Si la fonction ne renvoie pas de résultat,


alors, on appelle directement la fonction f(x);

Prof. R. HANNANE (FSSM) Programmation II 20 / 47


Les Fonctions en C

Exemple applecatif d’une fonction en C


# include < stdio .h >
/** *** le programme principal ( fonction main ) **** */
int main () {
int fplus ( int , int ) ; /* D é claration de la fonction fplus . */
int a , b , c ;
printf ( " Veuillez saisir le premier entier : " );
scanf ( " % d " ,& a );

printf ( " Veuillez saisir le deuxieme entier : " );


scanf ( " % d " ,& b );
/* Appel de la fonction fplus avec les arguments a et b */
c = fplus ( a , b ) ;
printf ( " La somme de % d et % d est : % d \ n " ,a ,b , c ) ;
return 0;
}
/** ************* D é finition de la fonction fplus ** * ** ** ** * ** ** * */
int fplus ( int x , int y ){
int val ; /* d é claration d ’ une variable " locale " à fplus */
val = x + y ;
return val ;
}

Prof. R. HANNANE (FSSM) Programmation II 21 / 47


Les Fonctions en C

L’instruction return
Quelques règles générales concernant cette instruction
L’instruction return peut mentionner n’importe quelle
expression
int fplus ( int x , int y ){
return x + y ;}

L’instruction return peut apparaı̂tre à plusieurs reprises


dans une fonction
int fplus ( int x , int y ){
int s = x + y ;
if (s >0) return ( s );
else return ( - s );
}

Si le type de l’expression figurant dans return est


différent du type du résultat tel qu’il a été déclaré dans
l’en-tête, le compilateur mettra automatiquement en place
des instructions de conversion
Prof. R. HANNANE (FSSM) Programmation II 22 / 47
Les Fonctions en C

Arguments muets et arguments effectifs


Arguments muets

Arguments muets
Les noms des arguments figurant dans l’en-tête de la
fonction se nomment des ”arguments muets”, ou encore
”arguments formels” ou ”paramètres formels”

⇒ Le rôle des arguments muets est de permettre, au sein du


corps de la fonction, de décrire ce qu’elle doit faire

/** ************* D é finition de la fonction fplus ** * ** ** ** * ** ** * */


int fplus ( int x , int y ){ /* x et y sont des arguments muets */
int val ; /* d é claration d ’ une variable " locale " à fplus */
val = x + y ;
return val ;
}

Prof. R. HANNANE (FSSM) Programmation II 23 / 47


Les Fonctions en C

Arguments muets et arguments effectifs


Arguments effectifs

Arguments effectifs
Les arguments fournis lors de l’utilisation (l’appel) de la
fonction se nomment des ”arguments effectifs” (ou encore
”paramètres effectifs”)
⇒ On peut utiliser n’importe quelle expression comme argument
effectif ; c’est la valeur de cette expression qui sera
transmise à la fonction lors de son appel

/* Appel de la fonction fplus avec les arguments a et b */


c = fplus ( a , b ) ; /* a et b sont des arguments effectifs */

Prof. R. HANNANE (FSSM) Programmation II 24 / 47


Les Fonctions en C

La transmission des arguments en C


Attention: Les arguments en C sont transmis par valeur
⇒ Quelle conséquence??
#i n c l u d e < s t d i o . h>
i n t main ( ) {
void echange ( int , i n t ) ;
i n t n =10 , p=20 ;
p r i n t f ( ” avant appel : %d %d\n” , n , p ) ;
echange (n , p ) ;
p r i n t f ( ” a p r è s a p p e l : %d %d” , n , p ) ;
return 0;
}
void echange ( i n t a , i n t b ){
p r i n t f ( ”dé b u t e c h a n g e : %d %d\n” , a , b ) ;
i n t c ; c=a ; a=b ; b=c ;
p r i n t f ( ” f i n e c h a n g e : %d %d\n” , a , b ) ;
}
/∗∗ ∗∗ A f f i c h a g e ∗∗∗∗ ∗/
/∗ a v a n t a p p e l : 10 20
dé b u t e c h a n g e : 10 20
f i n echange : 20 10
a p r è s a p p e l : 10 20 ∗/
Prof. R. HANNANE (FSSM) Programmation II 25 / 47
Les Fonctions en C

La transmission des arguments en C


Transmission par valeur: Explication
La fonction echange reçoit deux valeurs correspondant à ses
deux arguments muets a et b
Elle effectue un échange de ces deux valeurs.
Mais, lorsque l’on est revenu dans le programme principal,
aucune trace de cet échange ne subsiste sur les arguments
effectifs n et p.
En effet, lors de l’appel de echange, il y a eu transmission de la
valeur des expressions n et p. On peut dire que ces valeurs ont
été recopiées localement dans la fonction echange dans des
emplacements nommés a et b
C’est sur ces copies qu’a travaillé la fonction echange, de sorte
que les valeurs des variables n et p n’ont, pas été modifiées.
C’est ce qui explique le résultat constaté.
Prof. R. HANNANE (FSSM) Programmation II 26 / 47
Les Fonctions en C

La transmission des arguments en C

Transmission par valeur: Problème


Que faire quand une fonction produise une ou plusieurs
valeurs en retour, autres que celle de la fonction
elle-même??

Transmission par valeur: Solution


1 Transmettre en argument la valeur de l’adresse d’une
variable.

2 Utiliser des variables globales, mais réservée à des cas


exceptionnels, compte tenu des risques qu’elle présente

Prof. R. HANNANE (FSSM) Programmation II 27 / 47


Les Fonctions en C

Les types de variables


Variables globales

En C, une variable globales est une variable commune


partagée par plusieurs fonctions
Les fonctions peuvent se contenter d’utiliser la valeur du
variable globale mais rien ne les empêchent de la modifier
# include < stdio .h >
int i ; /* i est une variable globale */
int main (){
void optimist ( void ) ;
for ( i =1 ; i <=2 ; ++ i )
optimist () ;
return 0;
}
void optimist ( void ) {
printf ( " il fait beau % d fois \ n " , i ) ; }
/* Affichage */
/* il fait beau 1 fois
il fait beau 2 fois */

Prof. R. HANNANE (FSSM) Programmation II 28 / 47


Les Fonctions en C

Les types de variables


Variables globales

Une variable globales est déclarée en dehors de la fonction


main. ⇒ Elle est alors connue de toutes les fonctions qui seront
compilées par la suite au sein du même programme source

Il est préférable de regrouper les déclarations de toutes les


variables globales au début du programme source
/* n et x sont accessibles | /* n et x sont maintenant
aux fonctions fct1 et fct2 | accessibles aux fonctions
mais pas au | et au programme
programme principal */ | /* principal aussi */
int main () {... return 0;} | int n ;
int n ; | float x ;
float x ; | int main () {... return 0;}
fct1 (...){....} | fct1 (...) {....}
fct2 (...) {....} | fct2 (...) {....}

Prof. R. HANNANE (FSSM) Programmation II 29 / 47


Les Fonctions en C

Les types de variables


Variables globales

Les variables globales existent pendant toute l’exécution du


programme dans lequel elles apparaissent

Leurs emplacements en mémoire sont parfaitement définis


lors de l’édition de liens.
⇒On traduit cela en disant qu’elles font partie de la classe
d’allocation statique

Ces variables se voient initialisées par défaut, avant le début


de l’exécution du programme, sauf si vous leur attribuez
explicitement une valeur initiale au moment de leur déclaration

Prof. R. HANNANE (FSSM) Programmation II 30 / 47


Les Fonctions en C

Les types de variables


Variables globales externe

La portée d’une variable globale semble limitée au fichier


source dans lequel elle a été définie

Supposez que l’on compile séparément ces deux fichiers source


/* fichier source1 */ | /* fichier source2 */
int x ; |
int main () {... return 0;} | fct2 (...) {....}
fct1 (...){....} | fct3 (...) {....}

Le langage C prévoit une déclaration permettant de


spécifier qu’une variable globale a déjà été définie dans un
autre fichier source en faisant
précéder notre second fichier source de la déclaration :
extern int x ;

Prof. R. HANNANE (FSSM) Programmation II 31 / 47


Les Fonctions en C

Les types de variables


Variables globales externe

⇒ Il devient possible de mentionner la variable globale x (déclarée


dans le premier fichier source) dans les fonctions fct2 et fct3.

Cette déclaration extern n’effectue pas de réservation


d’emplacement de variable. Elle ne fait que préciser que la
variable globale x est définie par ailleurs et elle en précise le type

Remarque:
Le terme ”global” illustre le partage entre plusieurs fonctions
tandis que le terme ”externe” illustre plutôt le partage entre
plusieurs fichiers source

Prof. R. HANNANE (FSSM) Programmation II 32 / 47


Les Fonctions en C

Les types de variables


Variables globales cachées

Il est possible de ”cacher” une variable globale, c’est-à-dire


de la rendre inaccessible (confidentielle) à l’extérieur du
fichier source où elle a été définie
⇒ on parle de ”variables globales confidentielles”). Il suffit pour
cela d’utiliser la déclaration static

Cette possibilité de cacher des variables globales peut s’avérer


précieuse lorsque vous êtes amené à développer un
ensemble de fonctions d’intérêt général qui doivent
partager des variables globales.

Prof. R. HANNANE (FSSM) Programmation II 33 / 47


Les Fonctions en C

Les types de variables


Variables locales

Une variable locale est déclarée au sein d’une fonction (qui


pouvait être main).
⇒ De telle variable est dite locales à la fonction dans laquelle
elle sont déclarée.

Les variables locales ne sont connues qu’à l’intérieur de la


fonction où elles sont déclarées
⇒ Leur portée est limitée à cette fonction

Prof. R. HANNANE (FSSM) Programmation II 34 / 47


Les Fonctions en C

Les types de variables


Variables locales

Les variables locales n’ont aucun lien avec des


variables globales de même nom ou avec d’autres
variables locales à d’autres fonctions

Des variables locales même si ils ont le même nom, n’ont


aucun rapport

Une variable locale d’une fonction a le même nom qu’une


variable globale, alors dans toute la définition de la fonction,
c’est la variable locale qui est considérée. Elle n’écrase pas la
variable globale, mais la masque

Prof. R. HANNANE (FSSM) Programmation II 35 / 47


Les Fonctions en C

Les types de variables


Variables locales

Note:
Une variable locale est détruite au sortie de la fonction
dans laquelle elle est déclarée

int n ;
int main (){
int p ;
...
return 0;
}
fct1 (){
int p ;
int n ;
}
/* Notez qu ’ il est impossible dans fct1 d ’ utiliser
la variable golobale n */

Prof. R. HANNANE (FSSM) Programmation II 36 / 47


Les Fonctions en C

Les types de variables


Variables locales automatiques

Les variables locales ont une durée de vie limitée à celle d’une
exécution de la fonction dans laquelle elles figurent

Leurs emplacements ne sont pas définis de manière permanente


comme ceux des variables globales. Un nouvel espace
mémoire leur est alloué à chaque entrée dans la fonction
et libéré à chaque sortie
⇒ On traduit cela en disant que la classe d’allocation de ces
variables est automatique

La conséquence immédiate de ce mode d’allocation est que les


valeurs des variables locales ne sont pas conservées d’un
appel au suivant
Prof. R. HANNANE (FSSM) Programmation II 37 / 47
Les Fonctions en C

Les types de variables


Variables locales statiques
Il est possible de demander d’attribuer un emplacement permanent
à une variable locale et qu’ainsi sa valeur se conserve d’un appel
au suivant.
⇒ Il suffit pour cela de la déclarer à l’aide du mot-clé static
# include < stdio .h >
int main (){
void fct ( void ) ;
int n ;
for ( n =1 ; n <=2 ; ++ n )
fct () ;
return 0;
}
void fct ( void ){
static int i ; /* les variables locales de classe statique
sont , par d é faut , initialis é es à z é ro */
++ i ;
printf ( " appel num é ro : % d \ n " , i ) ;
} /** ****** Affichage ******** */
/* appel num é ro : 1
appel num é ro : 2 */

Prof. R. HANNANE (FSSM) Programmation II 38 / 47


Les Fonctions en C

Les types de variables

Récapulatif des types de variables


Une variable peut être déclarée soit:
I Localement dans la fonction qu’elle appelle.

⇒ Elle est dans ce cas, disponible juste à l’intérieur de cette


fonction

I Globalement au début du programme, juste aprés


l’instruction # include

⇒ Elle est dans ce cas,


disponible à toutes les fonctions du programme

Prof. R. HANNANE (FSSM) Programmation II 39 / 47


Les Fonctions en C

Les types de variables

Exercice1: A résoudre chez vous


Ecrire un programme qui demande à l’utilisateur de saisir les
valeurs de deux variable locales A et B. Ensuite, il permet de
définir et d’appeler les fonctions suivantes:
a. Une fonction qui retourne si les valeurs de A et B sont de même
signe ou non. (fonction sans valeur de retour et avec arguments)

b. Une fonction qui renvoie le minimum de A et B. (une fonction


avec valeur de retour et avec arguments)

c. Une fonction qui renvois le maximum de A et B. (une fonction


avec une valeur de retour et avec arguments)

Prof. R. HANNANE (FSSM) Programmation II 40 / 47


Les Fonctions en C

Les fonctions récursives

Une fonction qui s’appelle elle même telle que la fonction


factorielle est appellé fonction récursive

C’est l’équivalent de la récurrence en mathématique

Le langage C autorise la récursivité des appels de fonctions.

La programmation récursive sert à remplacer les boucles (while,


for, etc)

La récursivité permet de ramener un problème à un


sous-problème qui est le problème lui-même avec des
données plus simples

Prof. R. HANNANE (FSSM) Programmation II 41 / 47


Les Fonctions en C

Les fonctions récursives

La récursivité en C peut prendre deux aspects:

I Récursivité directe: une fonction comporte dans sa


définition au moins un appel à elle-même

I Récursivité croisée: l’appel d’une fonction entraı̂ne celui


d’une autre fonction qui à son tour appelle la fonction
initiale (le cycle pouvant d’ailleurs faire intervenir plus de
deux fonctions)

Prof. R. HANNANE (FSSM) Programmation II 42 / 47


Les Fonctions en C

Les fonctions récursives


La recette de la récursivité

1 S’assurer que le problème peut se décomposer en un ou


plusieurs sous-problèmes de même nature.

2 Identifier le cas de base qui est le plus petit problème qui ne


se décompose pas en sous-problèmes
3 Résoudre (P) =
I Si P est un cas de base,⇒ le résoudre directement
I Sinon
Décomposer P en sous-problèmes P1, P2,...
Résoudre récursivement P1, P2,...
Combiner les résultats pour obtenir la solution pour P

Prof. R. HANNANE (FSSM) Programmation II 43 / 47


Les Fonctions en C

Les fonctions récursives

Exemple de fonction récursive: Fonction factorielle


long fact ( int n )
{
if (n >1)
return ( fact (n -1)* n ) ;
else
return (1);
}

Par exemple, la fonction factorielle peut être définie sous forme


récursive de la maniére suivante:
I si n>1 alors factorielle(n)=n*factorielle(n-1) sinon
factorielle(n)=1
Lorsque n >1, il y a récursivité car la définition de factorielle(n)
fait appel à factorielle(n-1).

Prof. R. HANNANE (FSSM) Programmation II 44 / 47


Les Fonctions en C

Les fonctions récursives


Remarque:
Chaque appel de fact entraı̂ne une allocation d’espace
pour les variables locales et pour son argument n
→ fact ne comporte aucune variable locale !!!
En réalité, il lui faut prévoir un emplacement destiné à
recevoir sa valeur de retour. Or chaque nouvel appel de
fact,à l’intérieur de fact, provoque une telle allocation, sans
que les emplacements précédents soient libérés. Il y a donc un
empilement des espaces alloués aux variables locales,
parallèlement à un empilement des appels de la fonction.

⇒ Ce n’est que lors de l’exécution de la première instruction


return que l’on commencera à ”dépiler” les appels et les
emplacements et donc à libérer de l’espace mémoire.
Prof. R. HANNANE (FSSM) Programmation II 45 / 47
Les Fonctions en C

Les fonctions récursives


Inconvénients:
Dépassement de capacité
I Tentative de stocker un nombre plus grand que ce que peut
contenir le type de votre variable
I Choisir un type approprié: Exemple, pour le calcul des factoriels
il vaut mieux utiliser long au lieu de int

Débordement de pile (stack overflow)


I Appels récursifs sont placés dans la pile du programme
I La taille de pile est assez limitée et fixée tout au long du
programme
I Grande taille de données → débordement de la pile →
sortie anormale du programme.
Prof. R. HANNANE (FSSM) Programmation II 46 / 47
Les Fonctions en C

Les fonctions récursives

Exercice2: Suite de Fibonacci: A résoudre chez vous



F (0) = 0

Dit = F (1) = 1 (1)

F (n) = F (n − 1) + F (n − 2), si n > 1

Prof. R. HANNANE (FSSM) Programmation II 47 / 47

Vous aimerez peut-être aussi