(2ème partie)

 Nous avons vu qu'un sous-programme est un regroupement d'actions, le nom du sous-programme correspond au nom de l'action complexe. La définition d'un sous-programme de type PROCEDURE est équivalente. De même pour un sous-programme de type FONCTION mais nous rajouterons le fait qu'il doit retourner un résultat.

 Distinction algorithmique :

 PROCEDURE = action (traitement)

 FONCTION = action + évaluation d'une expression en retour (résultat)


Exemple : soit un sous-programme calculant le maximum de 2 entiers

PROCEDURE MAXIMUM (ENTREE X, ENTREE Y, SORTIE MAX) DEBUT  SI X > Y ALORS  MAX X;  SINON  MAX Y;  FIN SI; FIN

 Pour l'appel, nous écrirons : MAXIMUM (A, B, MAX_AB) ce qui est correct mais il vaut mieux passer par l'écriture d'une fonction.

FONCTION MAXIMUM (ENTREE X, ENTREE Y) DEBUT  SI X > Y ALORS  RETOURNER X;  SINON  RETOURNER Y;  FIN SI; FIN

 Appel du sous-programme : MAX_AB MAXIMUM(A,B);



Exemple : somme de 2 maximums

// Version avec procédure MAXIMUM (A, B, MAX_AB); MAXIMUM (C, D, MAX_CD); MAX MAX_AB + MAX_CD; // Version avec fonction MAX MAXIMUM (A, B) + MAXIMUM (C, D);

 Une fonction délivre un et un seul résultat. Nous souhaiterions néanmoins pouvoir renvoyer plusieurs résultats. Par exemple, pour des opérations de manipulation des nombres complexes (partie réelle et partie imaginaire), ou l'opération de division (quotient et reste) etc...

 Nous connaissons déjà un outil pouvant répondre à nos besoins : l'enregistrement (regroupement de données). Mais c'est insuffisant car il peut exister des cas pour lesquels les résultats souhaités ne pourront pas être regroupés dans un enregistrement :


Exemple :

Rechercher séquentiellement un élément X dans une table TAB, nous avons 2 résultats possibles :

- un indicateur TROUVE indiquant s'il existe une occurrence de X dans TAB
- si X existe dans TAB, un indice INDICE tel que TAB[INDICE] = X

Sous-programme de type procédure (action) // rechercher séquentiellement X dans une table TAB // résultat : // TROUVE = FAUX et INDICE n'est pas significatif // TROUVE = VRAI et TAB[INDICE] = X PROCEDURE RECHERCHER_ELEMENT (ENTREE TAB, ENTREE X, SORTIE TROUVE, SORTIE INDICE)

Exemple :

PROGRAMME BIZARRE GLOSSAIRE  A : tableau de 10 éléments;  I : indice du tableau A; FONCTION F (MISE A JOUR I) DEBUT  I I * 5;  RETOURNER I; FIN DEBUT  // Étape 1  I 1;  // Étape 2  A[I] F(I) * I + I;  // Étape 3  ECRIRE (A[I]); FIN

 Normalement le programme devrait exécuter l'affectation + écriture de l'élément A[1], mais nous avons une évaluation de la fonction F avec mise à jour de la variable I. La question que l'on peut se poser est : I = 1 ou I = 5 ? Une seule réponse : cela dépend du compilateur ! En général, l'évaluation se fera en premier et nous aurons par conséquent l'affectation de l'élément A[5].

 Une solution à ce problème peut s'écrire :

FONCTION F (ENTREE I) DEBUT  RETOURNER I*5; FIN

 L'effet de bord est un phénomène lié à la modification des variables globales. Les variables globales sont visibles dans un sous-programme, on peut donc les modifier dans le corps d'un sous-programme (voir portée des variables)

Attention à la modification des variables globales.

Exemple : soit la fonction F

FONCTION F (ENTREE X) DEBUT  M M + 1;  RETOURNER (M*X); FIN Avec M variable globale déclarée dans le programme principal

 Soient les séquences de code suivante :

// première séquence M 1; N F(5) + F(6); ECRIRE (N); // deuxième séquence M 1; N F(6) + F(5); ECRIRE (N);

Trace d'exécution de la 1ère séquence	Trace d'exécution de la 2ème séquence
M = 1	M = 1
Appel de la fonction F avec 5	Appel de la fonction F avec 6
M = 2	M = 2
F(5) retourne 10	F(6) retourne 12
Appel de F(6)	Appel de F(5)
M = 3	M = 3
F(6) retourne 18	F(5) retourne 15
N : 28	N : 27

 Conclusion : F(5) + F(6) n'est pas égal à F(6) + F(5), cette addition n'est pas commutative !!

 Le résultat de la fonction F dépend du contexte d'appel. Plusieurs appels identiques de la même fonction peuvent conduire à des résultats différents (effet de bord).


Autre exemple :

PROGRAMME EFFET_DE_BORD GLOSSAIRE  A : une variable globale;  B : une autre variable globale;  Z : une autre variable globale; PROCEDURE MAUVAIS_CARRE (ENTREE X, MISE A JOUR Y) DEBUT  Y 0;  Z X;  TANT QUE Z /= 0 FAIRE  Y X + Y;  Z Z - 1;  FIN TANT QUE; FIN DEBUT  // Étape 1  A 3; B 0; MAUVAIS_CARRE(A, B); ECRIRE(B);  // Étape 2  A 3; Z 0; MAUVAIS_CARRE(A, Z); ECRIRE(Z); FIN

Trace d'exécution du programme EFFET_DE_BORD
Etape 1	Programme EFFET_DE_BORD Sous-programme MAUVAIS_CARRE A = 3 X = 3 B = 0 Y référence sur B = 0 Z = ?
Exécution du sous-programme MAUVAIS_CARRE	B : 0, 0, 3, 6, 9 Z : ?, 3, 2, 1, 0
Résultat ECRIRE(B)	9 (Y = X² par additions successives de X)
Etape 2	Programme EFFET_DE_BORD Sous-programme MAUVAIS_CARRE A = 3 X = 3 B = ?   Z = 0 Y référence sur Z = 0
Exécution du sous-programme MAUVAIS_CARRE	Z : 0, 0, 3, 6, 5, 8, ... : Boucle infinie !!

 Nous assistons dans le cas présent au phénomène d'effet de bord : modification indésirable d'une variable globale (ici le paramètre formel Y et la variable Z désignant le même objet Z). Solution : réduire les affectations des variables globales.

 Déclarer la variable Z globale pour l'appel MAUVAIS_CARRE(A,Z) mais la variable Z du sous-programme MAUVAIS_CARRE doit être locale au sous-programme (pas de confusion entre Z global et Z local)

PROCEDURE MAUVAIS_CARRE (ENTREE X, MISE A JOUR Y) GLOSSAIRE  Z : variable locale au sous-programme pour compter le nombre d'additions successives de X; DEBUT  Même corps de sous-programme que dans l'exemple précédent FIN

 Règle d'utilisation des variables globales :

 Lorsqu'un programme est décomposé en plusieurs sous-programmes, les modifications (affectations) des variables globales ne doivent apparaître que dans un petit nombre de sous-programmes. Par contre tous les sous-programmes peuvent lire le contenu de la variable globale. Préférer l'utilisation des paramètres et des variables locales.

 Définition : La récursivité permet à une entité de se définir en fonction d'elle-même.

 En informatique nous retrouvons la notion de récursivité dans 2 cas : algorithmes récursifs (sous-programmes récursifs), structures de données récursives.


Exemple : créature blessée à la recherche d'une potion de vitalité

Solution récursive : soit la primitive avancer d'un pas AVANCER_UN_PAS définie par : // déplacement de la créature dans la direction de la potion d'une distance égale à PAS PROCEDURE AVANCER_UN_PAS (SORTIE PAS) // rechercher la potion PROCEDURE AVANCER_VERS_POTION (ENTREE DISTANCE_A_POTION) DEBUT  SI DISTANCE_A_POTION > 1 ALORS  AVANCER_UN_PAS(PAS);  AVANCER_VERS_POTION(DISTANCE_A_POTION - PAS);  FIN SI; FIN

 Nous avons le même problème que pour les répétitions : arrêt de la récursivité.

 Expression récursive :

• La branche terminale correspond à l'arrêt de la récursivité : il s'agit de l'expression du problème résolu (ex : si DISTANCE_A_POTION <= 1, la créature est arrivée à la potion et comme nous avons une sélection réduite l'action qui en découle sera de ne rien faire)
  
  
• La branche récursive est l'expression du même problème mais celui-ci doit être restreint par rapport au problème initial, sinon nous aurons une infinité d'appels récursifs.

Exemple :

Le problème est : AVANCER_VERS_POTION(DISTANCE_A_POTION)
Le problème restreint : AVANCER_VERS_POTION(DISTANCE_A_POTION - PAS)

Exemple d'exécution :

On considère que la créature est à une distance de 7 mètres de la potion, et que AVANCER_UN_PAS retourne toujours la valeur 2 mètres pour PAS

Soit D = DISTANCE_A_POTION

Exemple d'exécution

D = 7

PAS = 2 D = 7 - 2 = 5

PAS = 2 D = 5 - 2 = 3

PAS = 2 D = 3 - 2 = 1

PAS = 2 D = 1

Retour

Retour

Retour

Retour

FIN

Page précédente

Retour en haut de page