Séance 5 — Les fonctions et procédures

Découper, nommer, appeler

Séance 5 d’Algorithmique : découper, nommer, appeler.
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

NoteNavigation conceptuelle

Amont. Les variables et l’affectation (Séance 1), les conditions (Séance 2), les boucles (Séance 3), les tableaux et leurs parcours : somme, recherche, maximum, inversion (Séance 4). Une fonction n’ajoute aucune instruction de calcul : elle donne un nom à un bloc d’instructions et le fait exécuter à la demande, sur des données chaque fois différentes.

Aval. Cette séance clôt le cours : les fonctions et les procédures rassemblent les outils des Séances 0 à 4 (variables, conditions, boucles, tableaux) en traitements nommés, écrits une fois et appelés autant de fois que nécessaire.

ImportantObjectifs
  • Découper un problème en traitements nommés, chacun écrit une fois.
  • Écrire et appeler une fonction : paramètres formels et effectifs, valeur rendue par Retourner.
  • Écrire et appeler une procédure ; choisir entre passage par valeur et passage en entrée-sortie (E/S).
  • Passer un tableau à une fonction ou à une procédure.
  • Dérouler un appel à la main avec la pile des appels, y compris des appels imbriqués.
  • Repérer trois erreurs : Retourner oublié, paramètre par valeur modifié en vain, variable locale utilisée hors de sa fonction.

Les conventions du pseudo-code

Les séances 1 à 4 ont fixé les instructions, les boucles et les tableaux. La présente séance ajoute deux formes de sous-programmes, la fonction et la procédure, leur appel, et deux modes de passage des paramètres. Le tableau ci-dessous rappelle les conventions déjà fixées et donne, sous le trait, les nouvelles.

Écriture Sens
\(x\leftarrow e\) ; Lire ; Écrire ; Si ; TantQue ; Pour ; Répéter instructions et boucles des séances 1 à 3
T : tableau[1..n] déntiers ; T[i] tableau de \(n\) cases d’indices 1 à \(n\) (Séance 4)
\(C_1\) ET \(C_2\) ; \(C_1\) OU \(C_2\) ; \(a\,/\,b\) les deux membres sont évalués ; un réel s’écrit avec au moins une décimale (11,6 ; 40,0)
Fonction f(a : entier, b : entier) : entier … FinFonction définit la fonction f : ses paramètres formels avec leur type, puis le type de la valeur rendue
Retourner \(e\) évalue \(e\), rend sa valeur au point d’appel et termine l’appel ; atteindre FinFonction sans Retourner est une erreur
Procédure p(…) … FinProcédure définit la procédure p, qui ne rend pas de valeur ; l’appel se termine à FinProcédure
z \(\leftarrow\) f(x, y + 1) ; p(x, y) appel d’une fonction dans une expression ; appel d’une procédure, seul sur sa ligne
paramètre sans mention passage par valeur : le paramètre formel reçoit une copie de la valeur effective ; un tableau est copié case par case
T : tableau[1..n] déntiers en paramètre \(n\) au plus égal à la taille du tableau effectif : le sous-programme traite ses \(n\) premières cases ; un \(n\) plus grand est une erreur
E/S a : entier ; E/S T : tableau[1..n] déntiers passage en entrée-sortie, dans une procédure : a désigne la variable effective (une variable ou une case), que chaque affectation de a modifie
Début … Fin le programme principal, écrit après les fonctions et les procédures ; l’exécution commence à Début

La notation E/S est celle des cours d’algorithmique qui distinguent les paramètres « en entrée » (données lues par le sous-programme) des paramètres « en entrée-sortie » (données lues, puis modifiées). Elle a deux avantages. Elle est écrite dans l’en-tête, devant chaque paramètre concerné : l’en-tête dit à lui seul quelles variables de l’appelant la procédure peut changer. Elle décrit l’usage, non le mécanisme : les langages réalisent ce passage par une référence ou par une adresse, mais l’algorithme n’a besoin que de savoir que la variable est lue à l’entrée et modifiée en sortie. Ces cours connaissent aussi un mode « en sortie » (S), pour un paramètre seulement écrit ; le présent cours ne l’utilise pas. Il réserve E/S aux procédures : une fonction rend son résultat par Retourner, et un appel placé dans une expression ne modifie ainsi aucune variable de l’appelant.

Dans une trace de ce document, les variables sont groupées par cadre d’appel : d’abord celles du programme principal, puis celles de chaque fonction ou procédure (le nom du cadre est écrit en italique au-dessus de ses colonnes). Les colonnes d’un cadre sont vides quand cet appel n’est pas en cours. La colonne « Pile » donne les appels en cours au-dessus du programme principal. La valeur écrite au pas est en gras, dans la colonne de la variable effectivement modifiée ; un paramètre E/S est noté \(\rightarrow\)x (il désigne x). Un tableau occupe une colonne : ses cases dans l’ordre des indices, la case écrite en rouge gras, les cases lues en orange. La colonne « Test » porte aussi la valeur rendue par Retourner.

Le découpage d’un problème

Raisons du découpage

Au lycée de Thiès, le bulletin d’une classe demande quatre traitements : lire les notes, calculer la moyenne, trouver la meilleure note, donner la mention. Avec les seuls outils des séances précédentes, l’algorithme du bulletin enchaîne ces traitements dans un seul bloc ; le calcul du maximum de la Séance 4 y est recopié pour chaque matière, avec ses variables maxi, pos et i. Chaque copie peut contenir sa propre erreur, et corriger le maximum oblige à retrouver toutes les copies.

Le découpage répond à ce problème : chaque traitement est écrit une fois, sous un nom, et le programme principal l’utilise autant de fois que nécessaire, sur des données chaque fois différentes. Trois gains en découlent. Le traitement se corrige à un seul endroit. Il se vérifie seul, sur quelques cas, avant d’être utilisé. Le programme principal se lit comme la liste des étapes du problème, sans le détail de chacune.

NoteSous-programme : fonction et procédure

Un sous-programme est un traitement écrit une fois, sous un nom, avec des paramètres ; il s’exécute à chaque appel, sur les valeurs données à l’appel. Une fonction calcule et rend une valeur (la moyenne, la meilleure note) ; une procédure agit sans rendre de valeur : elle écrit, ou modifie des variables de l’appelant (lire les notes dans un tableau).

Le choix entre les deux formes se fait sur le résultat attendu. Si le traitement produit une valeur qui servira dans un calcul, une comparaison ou un Écrire, c’est une fonction : moy \(\leftarrow\) moyenne(notes, 5). Si le traitement change l’état de variables existantes (échanger deux valeurs, inverser un tableau), c’est une procédure.

La fonction

En-tête, paramètres, valeur rendue

Une fonction s’écrit avant le programme principal. Son en-tête donne son nom, la liste de ses paramètres avec leur type, et le type de la valeur qu’elle rend. Le corps suit, en retrait, et se termine par FinFonction. L’instruction Retourner \(e\) évalue \(e\) et rend sa valeur au point où la fonction a été appelée.

NoteParamètres formels et effectifs

Les paramètres formels sont les noms écrits dans l’en-tête (a, b). Les paramètres effectifs sont les expressions écrites dans l’appel : dans z \(\leftarrow\) max2(x, y), ce sont x et y. À l’appel, chaque formel reçoit, dans l’ordre, la valeur de son effectif ; il faut autant d’effectifs que de formels.

Un effectif peut être une constante, une variable ou une expression : max2(x - 10, 1) est un appel valide, où a reçoit la valeur de x - 10. Les noms des formels n’ont aucun lien avec ceux de l’appelant : max2 pourrait être appelée sur deux variables nommées a et b, ou sur prix1 et prix2. C’est la position dans la liste qui associe un effectif à un formel.

L’appel et le cadre d’appel

Pour exécuter un appel, il faut un endroit où ranger les paramètres et les variables de la fonction. Cet endroit est le cadre d’appel : créé au début de l’appel, il contient les paramètres formels, qui reçoivent les valeurs des effectifs, et les variables que la fonction affecte. Il disparaît quand l’appel se termine. Un appel f(e1, e2) se déroule toujours dans le même ordre :

  1. évaluer les effectifs e1 et e2, avec les variables de l’appelant ;
  2. créer le cadre d’appel de f et y copier ces valeurs dans les formels ;
  3. exécuter le corps de f, à partir de sa première instruction, jusqu’à un Retourner ;
  4. retirer le cadre d’appel et reprendre l’exécution à la ligne de l’appel, où la valeur rendue remplace f(e1, e2).

Exemple pas à pas : le maximum de deux nombres

L’algorithme suivant définit max2, puis l’appelle deux fois.

Fonction max2(a : entier, b : entier) : entier
  Si a ≥ b Alors
    m ← a
  Sinon
    m ← b
  FinSi
  Retourner m
FinFonction
Début
  x ← 12
  y ← 17
  z ← max2(x, y)
  Écrire "maximum :", z
  Écrire max2(x - 10, 1)
Fin
principal max2
Pas Ligne Instruction Pile x y z a b m Test Écrit
1 10 x ← 12 – 12
2 11 y ← 17 – 12 17
3 12 z ← max2(x, y) max2 12 17 12 17
4 2 Si a ≥ b Alors max2 12 17 12 17 faux
5 5 m ← b max2 12 17 12 17 17
6 7 Retourner m max2 12 17 12 17 17 rend 17
7 12 z ← max2(x, y) – 12 17 17
8 13 Écrire “maximum :”, z – 12 17 17 maximum : 17
9 14 Écrire max2(x - 10, 1) max2 12 17 17 2 1
10 2 Si a ≥ b Alors max2 12 17 17 2 1 vrai
11 3 m ← a max2 12 17 17 2 1 2
12 7 Retourner m max2 12 17 17 2 1 2 rend 2
13 14 Écrire max2(x - 10, 1) – 12 17 17 2

Les pas 1 et 2 affectent les variables du programme principal. Au pas 3, la ligne 12 appelle max2(x, y) : un cadre d’appel est créé, où a reçoit 12 et b reçoit 17 (en gras dans les colonnes de max2). L’exécution passe dans le corps de la fonction : le test \(12\geq17\) est faux (pas 4), m reçoit 17 (pas 5), et la ligne 7 rend 17 (pas 6). Le cadre d’appel est alors retiré : au pas 7, les colonnes de max2 sont vides, et z reçoit la valeur rendue. Le second appel, à la ligne 14 (pas 9), crée un nouveau cadre, avec \(\texttt{a}=2\) et \(\texttt{b}=1\) ; rien n’y reste du premier appel. La fonction rend 2 (pas 12) et Écrire l’écrit directement : une valeur rendue peut servir sans passer par une variable.

Pas 3 : l’appel empile le cadre de max2.

Pas 7 : le cadre est retiré, z reçoit 17.

AvertissementLa valeur rendue n’est pas une variable de l’appelant

Après z \(\leftarrow\) max2(x, y), le programme principal connaît z, mais pas m : m vivait dans le cadre d’appel, retiré au retour (section Section 6.3). Pour garder la valeur rendue, il faut l’affecter à une variable de l’appelant, ou l’utiliser dans l’instruction même de l’appel.

Le passage par valeur

Les paramètres de max2 sont passés par valeur : le formel reçoit une copie de la valeur effective. La fonction peut modifier ses paramètres, mais elle ne modifie que sa copie ; la variable effective de l’appelant ne change pas. Ce mode est le mode par défaut : c’est celui de tout paramètre écrit sans mention. Il garantit qu’une fonction ne dépend que des valeurs qu’elle reçoit et ne change aucune variable de l’appelant ; l’appel max2(x, y) laisse x et y intacts.

Exemple pas à pas : un tableau en paramètre

La moyenne d’un tableau de la Séance 4 devient une fonction : elle reçoit le tableau et sa taille, et rend un réel. Le tableau notes contient les notes d’Awa, à Kaolack, dans cinq matières.

Fonction moyenne(T : tableau[1..n] d'entiers,
    n : entier) : réel
  s ← 0
  Pour i de 1 à n Faire
    s ← s + T[i]
  FinPour
  Retourner s / n
FinFonction
Début
  notes : tableau[1..5] d'entiers
  notes ← [12, 8, 15, 9, 14]
  moy ← moyenne(notes, 5)
  Écrire "moyenne :", moy
Fin
principal moyenne
Pas Ligne Instruction Pile notes moy T n s i Test Écrit
1 10 notes : tableau[1..5] déntiers – · · · · ·
2 11 notes ← [12, 8, 15, 9, 14] – 12 8 15 9 14
3 12 moy ← moyenne(notes, 5) moyenne 12 8 15 9 14 12 8 15 9 14 5
4 3 s ← 0 moyenne 12 8 15 9 14 12 8 15 9 14 5 0
5 4 Pour i de 1 à n Faire moyenne 12 8 15 9 14 12 8 15 9 14 5 0 1 vrai
6 5 s ← s + T[i] moyenne 12 8 15 9 14 12 8 15 9 14 5 12 1
7 4 Pour i de 1 à n Faire moyenne 12 8 15 9 14 12 8 15 9 14 5 12 2 vrai
8 5 s ← s + T[i] moyenne 12 8 15 9 14 12 8 15 9 14 5 20 2
9 4 Pour i de 1 à n Faire moyenne 12 8 15 9 14 12 8 15 9 14 5 20 3 vrai
10 5 s ← s + T[i] moyenne 12 8 15 9 14 12 8 15 9 14 5 35 3
11 4 Pour i de 1 à n Faire moyenne 12 8 15 9 14 12 8 15 9 14 5 35 4 vrai
12 5 s ← s + T[i] moyenne 12 8 15 9 14 12 8 15 9 14 5 44 4
13 4 Pour i de 1 à n Faire moyenne 12 8 15 9 14 12 8 15 9 14 5 44 5 vrai
14 5 s ← s + T[i] moyenne 12 8 15 9 14 12 8 15 9 14 5 58 5
15 4 Pour i de 1 à n Faire moyenne 12 8 15 9 14 12 8 15 9 14 5 58 6 faux
16 7 Retourner s / n moyenne 12 8 15 9 14 12 8 15 9 14 5 58 rend 11,6
17 12 moy ← moyenne(notes, 5) – 12 8 15 9 14 11,6
18 13 Écrire “moyenne :”, moy – 12 8 15 9 14 11,6 moyenne : 11,6

Au pas 3, l’appel crée le cadre de moyenne : T reçoit une copie des cinq cases de notes (en rouge, toutes écrites par l’appel), et n reçoit 5. La boucle lit les cases de cette copie (en orange) et accumule 12, 20, 35, 44, puis 58. La ligne 7 rend \(58/5=11{,}6\) (pas 16), un réel, et moy le reçoit au pas 17. Le tableau notes n’a pas changé : passé par valeur, il a été copié, et la fonction a travaillé sur la copie. L’en-tête déclare T : tableau[1..n] déntiers : la taille de la copie est celle de l’effectif, ici 5, et l’appel donne la même valeur à n. Avec un n plus petit que la taille, la fonction traite les \(n\) premières cases : moyenne(notes, 4) rend \(44/4=11{,}0\), et l’algorithme écrit alors moyenne : 11,0. Un n plus grand que la taille, comme moyenne(notes, 6), est un appel incorrect.

AvertissementChoix du cours (celui de Pascal)

En C, Java et Python, un tableau passé en paramètre n’est pas copié : ses cases modifiées le sont chez l’appelant, comme en E/S. Le cours copie le tableau passé par valeur, pour qu’une seule règle vaille pour tous les paramètres.

Exemple pas à pas : une recherche rendue par une fonction

La recherche avec arrêt de la Séance 4 devient elle aussi une fonction, qui rend la position de x dans T, ou 0 si x est absent. Le tableau C contient les numéros des colis du jour à la gare routière de Kaolack. Une première version reprend le TantQue de la Séance 4.

Fonction position(T : tableau[1..n] d'entiers,
    n : entier, x : entier) : entier
  pos ← 0
  i ← 1
  TantQue i ≤ n ET pos = 0 Faire
    Si T[i] = x Alors
      pos ← i
    FinSi
    i ← i + 1
  FinTantQue
  Retourner pos
FinFonction
Début
  C : tableau[1..5] d'entiers
  C ← [305, 112, 478, 260, 391]
  p ← position(C, 5, 478)
  Écrire "case :", p
Fin

La trace compte 19 pas ; la boucle fait 4 tests et 3 comparaisons, et la ligne 11 rend 3. Une seconde version utilise une propriété de Retourner : l’instruction termine l’appel, même au milieu d’une boucle. La boucle peut donc être un Pour sur toutes les cases, arrêté par Retourner dès que la case est trouvée.

Fonction position(T : tableau[1..n] d'entiers,
    n : entier, x : entier) : entier
  Pour i de 1 à n Faire
    Si T[i] = x Alors
      Retourner i
    FinSi
  FinPour
  Retourner 0
FinFonction
Début
  C : tableau[1..5] d'entiers
  C ← [305, 112, 478, 260, 391]
  p ← position(C, 5, 478)
  Écrire "case :", p
Fin
principal position
Pas Ligne Instruction Pile C p T n x i Test Écrit
1 11 C : tableau[1..5] déntiers – · · · · ·
2 12 C ← [305, 112, 478, 260, 391] – 305 112 478 260 391
3 13 p ← position(C, 5, 478) position 305 112 478 260 391 305 112 478 260 391 5 478
4 3 Pour i de 1 à n Faire position 305 112 478 260 391 305 112 478 260 391 5 478 1 vrai
5 4 Si T[i] = x Alors position 305 112 478 260 391 305 112 478 260 391 5 478 1 faux
6 3 Pour i de 1 à n Faire position 305 112 478 260 391 305 112 478 260 391 5 478 2 vrai
7 4 Si T[i] = x Alors position 305 112 478 260 391 305 112 478 260 391 5 478 2 faux
8 3 Pour i de 1 à n Faire position 305 112 478 260 391 305 112 478 260 391 5 478 3 vrai
9 4 Si T[i] = x Alors position 305 112 478 260 391 305 112 478 260 391 5 478 3 vrai
10 5 Retourner i position 305 112 478 260 391 305 112 478 260 391 5 478 3 rend 3
11 13 p ← position(C, 5, 478) – 305 112 478 260 391 3
12 14 Écrire “case :”, p – 305 112 478 260 391 3 case : 3

Au pas 9, le test \(478=478\) est vrai ; au pas 10, Retourner i rend 3 et termine l’appel : le Pour ne fait pas ses tours 4 et 5, et la ligne 8 n’est pas exécutée. La trace compte 12 pas, pour les mêmes 3 comparaisons. Quand x est absent (position(C, 5, 200)), le Pour va jusqu’au bout, avec 5 comparaisons, et la ligne 8 rend 0. Les deux versions rendent le même résultat ; la seconde n’a besoin ni de pos, ni d’une double condition d’arrêt, parce que le retour joue le rôle de l’arrêt.

La procédure et le passage des paramètres

La procédure

Certains traitements ne calculent pas une valeur : ils changent l’état de variables existantes. Échanger deux variables, inverser un tableau, remplir un tableau par Lire, écrire un ticket : le résultat est un effet, non une valeur. Ces traitements s’écrivent en procédures.

NoteProcédure

Une procédure se définit par Procédure nom(paramètres) … FinProcédure. Elle ne rend pas de valeur et ne contient pas de Retourner. Son appel est une instruction seule sur sa ligne, echanger(x, y) ; il se termine quand l’exécution atteint FinProcédure, et l’algorithme reprend à la ligne qui suit l’appel.

Exemple pas à pas : un échange par valeur, sans effet

Une première procédure d’échange reprend les trois affectations de la Séance 4, avec deux paramètres passés par valeur.

Procédure echanger(a : entier,
    b : entier)
  tmp ← a
  a ← b
  b ← tmp
FinProcédure
Début
  x ← 5
  y ← 9
  echanger(x, y)
  Écrire x, y
Fin
principal echanger
Pas Ligne Instruction Pile x y a b tmp Test Écrit
1 8 x ← 5 – 5
2 9 y ← 9 – 5 9
3 10 echanger(x, y) echanger 5 9 5 9
4 3 tmp ← a echanger 5 9 5 9 5
5 4 a ← b echanger 5 9 9 9 5
6 5 b ← tmp echanger 5 9 9 5 5
7 6 FinProcédure echanger 5 9 9 5 5
8 11 Écrire x, y – 5 9 5 9

L’échange a bien lieu, mais dans le cadre d’appel : au pas 6, a vaut 9 et b vaut 5. Au pas 7, FinProcédure retire le cadre, et les valeurs échangées disparaissent avec lui. Les colonnes x et y n’ont jamais changé : a et b n’étaient que des copies, et l’algorithme écrit 5 9. Aucune erreur n’est signalée : la procédure fait exactement ce qui est écrit, sur ses copies.

Le passage en entrée-sortie

Pour qu’une procédure modifie une variable de l’appelant, le paramètre doit désigner cette variable elle-même, et non une copie.

NotePassage en entrée-sortie (E/S)

Un paramètre écrit E/S a : entier est passé en entrée-sortie, ou par référence : dans le cadre d’appel, a désigne la variable effective (a \(\rightarrow\) x). Lire a, c’est lire x ; affecter a, c’est affecter x. L’effectif doit être une variable ou une case de tableau : echanger(x, 3) est un appel incorrect.

Procédure echanger(E/S a : entier,
    E/S b : entier)
  tmp ← a
  a ← b
  b ← tmp
FinProcédure
Début
  x ← 5
  y ← 9
  echanger(x, y)
  Écrire x, y
Fin
principal echanger
Pas Ligne Instruction Pile x y a b tmp Test Écrit
1 8 x ← 5 – 5
2 9 y ← 9 – 5 9
3 10 echanger(x, y) echanger 5 9 \(\rightarrow\)x \(\rightarrow\)y
4 3 tmp ← a echanger 5 9 \(\rightarrow\)x \(\rightarrow\)y 5
5 4 a ← b echanger 9 9 \(\rightarrow\)x \(\rightarrow\)y 5
6 5 b ← tmp echanger 9 5 \(\rightarrow\)x \(\rightarrow\)y 5
7 6 FinProcédure echanger 9 5 \(\rightarrow\)x \(\rightarrow\)y 5
8 11 Écrire x, y – 9 5 9 5

Au pas 3, le cadre d’appel ne contient pas de valeurs pour a et b, mais deux renvois : a désigne x, b désigne y. Au pas 5, a \(\leftarrow\) b lit y, qui vaut 9, et écrit dans x : c’est la colonne x qui passe en gras. Au pas 6, b \(\leftarrow\) tmp écrit 5 dans y. Seule tmp est une variable du cadre d’appel, retiré au pas 7. L’algorithme écrit 9 5.

Par valeur, pas 6 : l’échange reste dans le cadre.

En E/S, pas 6 : y reçoit 5 dans le principal.

Exemple pas à pas : un tableau en entrée-sortie

Un tableau passé en E/S n’est pas copié : le formel désigne le tableau effectif, et la procédure modifie ses cases. L’inversion de la Séance 4 devient une procédure, appelée sur les numéros des tickets d’une file d’attente.

Procédure inverser(E/S T : tableau[1..n] d'entiers,
    n : entier)
  Pour i de 1 à n div 2 Faire
    tmp ← T[i]
    T[i] ← T[n - i + 1]
    T[n - i + 1] ← tmp
  FinPour
FinProcédure
Début
  F : tableau[1..4] d'entiers
  F ← [17, 23, 31, 42]
  inverser(F, 4)
  Écrire F[1], F[2], F[3], F[4]
Fin
principal inverser
Pas Ligne Instruction Pile F T n i tmp Test Écrit
1 10 F : tableau[1..4] déntiers – · · · ·
2 11 F ← [17, 23, 31, 42] – 17 23 31 42
3 12 inverser(F, 4) inverser 17 23 31 42 \(\rightarrow\)F 4
4 3 Pour i de 1 à n div 2 Faire inverser 17 23 31 42 \(\rightarrow\)F 4 1 vrai
5 4 tmp ← T[i] inverser 17 23 31 42 \(\rightarrow\)F 4 1 17
6 5 T[i] ← T[n - i + 1] inverser 42 23 31 42 \(\rightarrow\)F 4 1 17
7 6 T[n - i + 1] ← tmp inverser 42 23 31 17 \(\rightarrow\)F 4 1 17
8 3 Pour i de 1 à n div 2 Faire inverser 42 23 31 17 \(\rightarrow\)F 4 2 17 vrai
9 4 tmp ← T[i] inverser 42 23 31 17 \(\rightarrow\)F 4 2 23
10 5 T[i] ← T[n - i + 1] inverser 42 31 31 17 \(\rightarrow\)F 4 2 23
11 6 T[n - i + 1] ← tmp inverser 42 31 23 17 \(\rightarrow\)F 4 2 23
12 3 Pour i de 1 à n div 2 Faire inverser 42 31 23 17 \(\rightarrow\)F 4 3 23 faux
13 8 FinProcédure inverser 42 31 23 17 \(\rightarrow\)F 4 23
14 13 Écrire F[1], F[2], F[3], F[4] – 42 31 23 17 42 31 23 17

La colonne T du cadre d’appel porte un seul renvoi, \(\rightarrow\)F : il n’y a qu’une rangée de cases, celle de F. Les affectations des lignes 5 et 6 écrivent dans les cases de F (en rouge dans la colonne du programme principal), et la boucle fait \(4\) div \(2=2\) tours. L’algorithme écrit 42 31 23 17.

Sans E/S devant T, le tableau est passé par valeur : la procédure inverse une copie, retirée à FinProcédure, et la même exécution écrit 17 23 31 42, le tableau de départ. La trace complète, de 14 pas comme la précédente, ne diffère que par la colonne où s’écrivent les cases :

principal inverser
Pas Ligne Instruction Pile F T n i tmp Test Écrit
1 10 F : tableau[1..4] déntiers – · · · ·
2 11 F ← [17, 23, 31, 42] – 17 23 31 42
3 12 inverser(F, 4) inverser 17 23 31 42 17 23 31 42 4
4 3 Pour i de 1 à n div 2 Faire inverser 17 23 31 42 17 23 31 42 4 1 vrai
5 4 tmp ← T[i] inverser 17 23 31 42 17 23 31 42 4 1 17
6 5 T[i] ← T[n - i + 1] inverser 17 23 31 42 42 23 31 42 4 1 17
7 6 T[n - i + 1] ← tmp inverser 17 23 31 42 42 23 31 17 4 1 17
8 3 Pour i de 1 à n div 2 Faire inverser 17 23 31 42 42 23 31 17 4 2 17 vrai
9 4 tmp ← T[i] inverser 17 23 31 42 42 23 31 17 4 2 23
10 5 T[i] ← T[n - i + 1] inverser 17 23 31 42 42 31 31 17 4 2 23
11 6 T[n - i + 1] ← tmp inverser 17 23 31 42 42 31 23 17 4 2 23
12 3 Pour i de 1 à n div 2 Faire inverser 17 23 31 42 42 31 23 17 4 3 23 faux
13 8 FinProcédure inverser 17 23 31 42 42 31 23 17 4 23
14 13 Écrire F[1], F[2], F[3], F[4] – 17 23 31 42 17 23 31 42

Une procédure qui en appelle une autre

Une procédure peut appeler une autre procédure, et un paramètre E/S peut désigner une case de tableau. L’inversion s’écrit alors avec la procédure echanger : chaque tour échange deux cases.

Procédure echanger(E/S a : entier,
    E/S b : entier)
  tmp ← a
  a ← b
  b ← tmp
FinProcédure
Procédure inverser(E/S T : tableau[1..n] d'entiers,
    n : entier)
  Pour i de 1 à n div 2 Faire
    echanger(T[i], T[n - i + 1])
  FinPour
FinProcédure
Début
  F : tableau[1..4] d'entiers
  F ← [17, 23, 31, 42]
  inverser(F, 4)
  Écrire F[1], F[2], F[3], F[4]
Fin
principal inverser echanger
Pas Ligne Instruction Pile F T n i a b tmp Test Écrit
1 14 F : tableau[1..4] déntiers – · · · ·
2 15 F ← [17, 23, 31, 42] – 17 23 31 42
3 16 inverser(F, 4) inverser 17 23 31 42 \(\rightarrow\)F 4
4 9 Pour i de 1 à n div 2 Faire inverser 17 23 31 42 \(\rightarrow\)F 4 1 vrai
5 10 echanger(T[i], T[n - i + 1]) inverser, echanger 17 23 31 42 \(\rightarrow\)F 4 1 \(\rightarrow\)T[1] \(\rightarrow\)T[4]
6 3 tmp ← a inverser, echanger 17 23 31 42 \(\rightarrow\)F 4 1 \(\rightarrow\)T[1] \(\rightarrow\)T[4] 17
7 4 a ← b inverser, echanger 42 23 31 42 \(\rightarrow\)F 4 1 \(\rightarrow\)T[1] \(\rightarrow\)T[4] 17
8 5 b ← tmp inverser, echanger 42 23 31 17 \(\rightarrow\)F 4 1 \(\rightarrow\)T[1] \(\rightarrow\)T[4] 17
9 6 FinProcédure inverser, echanger 42 23 31 17 \(\rightarrow\)F 4 1 \(\rightarrow\)T[1] \(\rightarrow\)T[4] 17
10 9 Pour i de 1 à n div 2 Faire inverser 42 23 31 17 \(\rightarrow\)F 4 2 vrai
11 10 echanger(T[i], T[n - i + 1]) inverser, echanger 42 23 31 17 \(\rightarrow\)F 4 2 \(\rightarrow\)T[2] \(\rightarrow\)T[3]
12 3 tmp ← a inverser, echanger 42 23 31 17 \(\rightarrow\)F 4 2 \(\rightarrow\)T[2] \(\rightarrow\)T[3] 23
13 4 a ← b inverser, echanger 42 31 31 17 \(\rightarrow\)F 4 2 \(\rightarrow\)T[2] \(\rightarrow\)T[3] 23
14 5 b ← tmp inverser, echanger 42 31 23 17 \(\rightarrow\)F 4 2 \(\rightarrow\)T[2] \(\rightarrow\)T[3] 23
15 6 FinProcédure inverser, echanger 42 31 23 17 \(\rightarrow\)F 4 2 \(\rightarrow\)T[2] \(\rightarrow\)T[3] 23
16 9 Pour i de 1 à n div 2 Faire inverser 42 31 23 17 \(\rightarrow\)F 4 3 faux
17 12 FinProcédure inverser 42 31 23 17 \(\rightarrow\)F 4
18 17 Écrire F[1], F[2], F[3], F[4] – 42 31 23 17 42 31 23 17

Au pas 5, l’appel echanger(T[i], T[n - i + 1]) crée un troisième cadre : a désigne T[1] et b désigne T[4], c’est-à-dire, puisque T désigne F, les cases 1 et 4 de F. Les affectations des pas 7 et 8 écrivent donc dans F. Pendant ces pas, trois appels sont en cours : le programme principal, inverser et echanger. Le résultat est celui de la version précédente ; la trace compte 18 pas, quatre de plus, pour les deux appels et les deux retours d’echanger.

AvertissementValeur ou E/S : choisir

Un paramètre que le sous-programme ne fait que lire se passe par valeur ; un paramètre qu’une procédure doit modifier pour l’appelant se passe en E/S. Modifier un paramètre par valeur pour changer l’appelant est sans effet, et sans message. À l’inverse, mettre E/S partout permet à la procédure de changer une variable que l’appelant croyait protégée.

Portée et pile des appels

Variables locales et portée

Les paramètres d’une fonction et les variables qu’elle affecte sont ses variables locales : elles n’existent que dans son cadre d’appel, donc seulement pendant l’appel. Leur portée, l’ensemble des instructions où elles sont connues, est le corps de la fonction. Une fonction ne voit pas non plus les variables du programme principal : elle ne connaît que ses paramètres et ses variables locales. Deux fonctions peuvent donc employer les mêmes noms sans se gêner ; deux variables de même nom dans deux cadres d’appel différents sont deux variables différentes.

Exemple pas à pas : deux variables i

Le programme principal écrit, pour \(i\) de 2 à 3, le nombre triangulaire \(1+2+\dots+i\), calculé par une fonction qui a, elle aussi, un compteur nommé i.

Fonction triangle(n : entier) : entier
  s ← 0
  Pour i de 1 à n Faire
    s ← s + i
  FinPour
  Retourner s
FinFonction
Début
  Pour i de 2 à 3 Faire
    Écrire i, triangle(i)
  FinPour
Fin
principal triangle
Pas Ligne Instruction Pile i n s i Test Écrit
1 9 Pour i de 2 à 3 Faire – 2 vrai
2 10 Écrire i, triangle(i) triangle 2 2
3 2 s ← 0 triangle 2 2 0
4 3 Pour i de 1 à n Faire triangle 2 2 0 1 vrai
5 4 s ← s + i triangle 2 2 1 1
6 3 Pour i de 1 à n Faire triangle 2 2 1 2 vrai
7 4 s ← s + i triangle 2 2 3 2
8 3 Pour i de 1 à n Faire triangle 2 2 3 3 faux
9 6 Retourner s triangle 2 2 3 rend 3
10 10 Écrire i, triangle(i) – 2 2 3
11 9 Pour i de 2 à 3 Faire – 3 vrai
12 10 Écrire i, triangle(i) triangle 3 3
13 2 s ← 0 triangle 3 3 0
14 3 Pour i de 1 à n Faire triangle 3 3 0 1 vrai
15 4 s ← s + i triangle 3 3 1 1
16 3 Pour i de 1 à n Faire triangle 3 3 1 2 vrai
17 4 s ← s + i triangle 3 3 3 2
18 3 Pour i de 1 à n Faire triangle 3 3 3 3 vrai
19 4 s ← s + i triangle 3 3 6 3
20 3 Pour i de 1 à n Faire triangle 3 3 6 4 faux
21 6 Retourner s triangle 3 3 6 rend 6
22 10 Écrire i, triangle(i) – 3 3 6
23 9 Pour i de 2 à 3 Faire – 4 faux

Pendant le premier appel (pas 2 à 9), la colonne i de triangle prend les valeurs 1, 2 et 3, tandis que celle du programme principal reste 2. Au retour, la case de triangle est retirée avec son i ; au pas 11, le Pour du programme principal augmente son i, qui passe à 3. Les deux lignes écrites, 2 3 et 3 6, montrent que le compteur du programme principal n’a pas été perturbé. Le formel n reçoit la valeur de i à chaque appel : 2, puis 3.

La pile des appels

Quand une fonction en appelle une autre, plusieurs appels sont en cours à la fois : le premier attend la valeur du second. Leurs cadres d’appel s’empilent.

NotePile des appels

La pile des appels (ou pile d’exécution) range les cadres d’appel des appels en cours, le programme principal en bas. Chaque appel y empile un cadre d’appel au sommet ; Retourner ou FinProcédure retire le cadre du sommet, et l’exécution reprend dans le cadre qui se trouve alors au sommet. Seul le cadre du sommet est actif : les instructions exécutées lisent et écrivent ses variables.

L’algorithme suivant calcule le maximum de trois températures relevées à Matam, par une fonction max3 qui appelle deux fois max2. Cette version de max2 utilise deux Retourner : le premier, dans le Si, termine l’appel quand \(a\geq b\) ; sinon, l’exécution atteint le second.

Fonction max2(a : entier, b : entier) : entier
  Si a ≥ b Alors
    Retourner a
  FinSi
  Retourner b
FinFonction
Fonction max3(a : entier, b : entier,
    c : entier) : entier
  m ← max2(a, b)
  Retourner max2(m, c)
FinFonction
Début
  t ← max3(31, 38, 35)
  Écrire "maximum :", t
Fin
principal max3 max2
Pas Ligne Instruction Pile t a b c m a b Test Écrit
1 13 t ← max3(31, 38, 35) max3 31 38 35
2 9 m ← max2(a, b) max3, max2 31 38 35 31 38
3 2 Si a ≥ b Alors max3, max2 31 38 35 31 38 faux
4 5 Retourner b max3, max2 31 38 35 31 38 rend 38
5 9 m ← max2(a, b) max3 31 38 35 38
6 10 Retourner max2(m, c) max3, max2 31 38 35 38 38 35
7 2 Si a ≥ b Alors max3, max2 31 38 35 38 38 35 vrai
8 3 Retourner a max3, max2 31 38 35 38 38 35 rend 38
9 10 Retourner max2(m, c) max3 31 38 35 38 rend 38
10 13 t ← max3(31, 38, 35) – 38
11 14 Écrire “maximum :”, t – 38 maximum : 38

Au pas 2, trois cadres sont empilés : le programme principal attend la valeur de max3, qui attend celle de max2. Le premier appel de max2 se termine au pas 4 par la ligne 5 ; son cadre retiré, max3 redevient active et m reçoit 38 (pas 5). Le second appel de max2 crée un nouveau cadre ; il se termine au pas 8, par le premier Retourner, puisque \(38\geq35\). Au pas 9, Retourner max2(m, c) de max3 rend la valeur que max2 vient de rendre, et la pile ne contient plus que le programme principal. Les variables a et b de max3 et celles de max2 portent les mêmes noms, mais vivent dans des cadres différents : au pas 2, a vaut 31 dans les deux cadres ; au pas 6, a vaut 38 dans max2 et toujours 31 dans max3.

AstuceMéthode : dérouler un appel à la main
  1. À l’appel, évaluer les effectifs dans le cadre actif, puis dessiner un cadre au sommet de la pile, avec un paramètre formel par ligne : une valeur pour un passage par valeur, un renvoi (\(\rightarrow\)x) pour un passage en E/S.
  2. Exécuter le corps en ne lisant et en n’écrivant que dans le cadre du sommet ; une affectation d’un paramètre E/S s’écrit dans la variable désignée.
  3. À Retourner ou FinProcédure, noter la valeur rendue, barrer le cadre du sommet et reprendre à la ligne de l’appel, dans le cadre qui est maintenant au sommet.

Erreurs fréquentes

L’oubli de Retourner

Une fonction doit exécuter un Retourner sur chacun de ses chemins. Si l’exécution atteint FinFonction, la fonction n’a aucune valeur à rendre, et l’instruction qui l’a appelée ne peut pas s’achever.

Fonction max2(a : entier, b : entier) : entier
  Si a ≥ b Alors
    m ← a
  Sinon
    m ← b
  FinSi
FinFonction
Début
  x ← 12
  y ← 17
  z ← max2(x, y)
  Écrire "maximum :", z
Fin
principal max2
Pas Ligne Instruction Pile x y a b m Test Écrit
1 9 x ← 12 – 12
2 10 y ← 17 – 12 17
3 11 z ← max2(x, y) max2 12 17 12 17
4 2 Si a ≥ b Alors max2 12 17 12 17 faux
5 5 m ← b max2 12 17 12 17 17
6 7 FinFonction max2 12 17 12 17 17 erreur arrêt : pas de Retourner

Le calcul du maximum est correct : au pas 5, m vaut 17. Mais le pas 6 atteint FinFonction sans Retourner : l’exécution s’arrête, et z ne reçoit rien. La correction ajoute Retourner m avant FinFonction. Une fonction qui contient un Retourner dans un Si doit en avoir un aussi pour le cas où le test est faux, comme la ligne 5 du max2 de la section Section 5.3.

Un paramètre par valeur modifié en vain

La section Section 4.2 l’a montré : une procédure qui modifie un paramètre passé par valeur ne modifie que sa copie, et l’appelant ne voit aucun changement. L’erreur est silencieuse ; seule la trace la révèle, avec des colonnes de l’appelant qui ne changent jamais. Le remède est le passage en E/S pour une procédure, ou, pour un calcul, une fonction qui rend la nouvelle valeur : x \(\leftarrow\) f(x).

Une variable locale utilisée hors de sa fonction

Une variable locale disparaît avec son cadre d’appel. Le programme principal ne peut donc pas l’utiliser après l’appel, même si la fonction vient de lui donner une valeur. Le prix de 3 kg de mangues à 750 F le kilo, au marché Tilène, en donne un exemple.

Fonction prix(q : entier,
    pu : entier) : entier
  total ← q × pu
  Retourner total
FinFonction
Début
  p ← prix(3, 750)
  Écrire "montant :", total
Fin
principal prix
Pas Ligne Instruction Pile p q pu total Test Écrit
1 7 p ← prix(3, 750) prix 3 750
2 3 total ← q × pu prix 3 750 2250
3 4 Retourner total prix 3 750 2250 rend 2250
4 7 p ← prix(3, 750) – 2250
5 8 Écrire “montant :”, total – 2250 erreur arrêt : total inconnue

Au pas 2, total reçoit 2250 dans le cadre de prix ; au pas 3, la fonction rend cette valeur et son cadre est retiré ; au pas 4, p reçoit 2250. Au pas 5, la ligne 8 demande total, qui n’est pas une variable du programme principal : l’exécution s’arrête. La valeur cherchée est dans p ; il faut écrire Écrire "montant :", p.

AvertissementLes trois erreurs et leur signe dans une trace

Retourner oublié : arrêt à FinFonction. Paramètre par valeur modifié pour changer l’appelant : aucun arrêt, mais les colonnes de l’appelant ne changent pas. Variable locale hors de sa fonction : arrêt sur une variable que le cadre actif ne connaît pas.

Exercices corrigés

Les trois exercices suivants reprennent les trois questions que pose tout sous-programme : que rend un appel, que modifie-t-il chez l’appelant, et quelle est la pile à un instant donné. Ils préparent la fiche de TD, dont les réponses se présentent de la même façon : trace, tableau résumé, conclusion.

Exercice 1 : deux appels d’une même fonction

Les membres d’une tontine de Thiès versent chaque mois une cotisation de 5000 F, ou moins quand le mois est difficile. Le tableau V contient les versements de cinq membres.

Fonction compter(T : tableau[1..n] d'entiers,
    n : entier, s : entier) : entier
  c ← 0
  Pour i de 1 à n Faire
    Si T[i] ≥ s Alors
      c ← c + 1
    FinSi
  FinPour
  Retourner c
FinFonction
Début
  V : tableau[1..5] d'entiers
  V ← [5000, 2000, 5000, 3000, 5000]
  a ← compter(V, 5, 5000)
  Écrire a, compter(V, 5, 3000) - a
Fin
  1. Pour l’appel de la ligne 14, relever, à chaque tour, T[i], le résultat du test de la ligne 5 et la valeur de c après le tour.
  2. Qu’écrit la ligne 15 ?
  3. Combien de cadres d’appel sont créés pendant l’exécution ? Combien de fois la ligne 9 est-elle exécutée ?
  4. Donner les paramètres formels et effectifs de l’appel de la ligne 15.
AstuceCorrection

(a) Règle appliquée. À l’appel, chaque formel reçoit la valeur de son effectif : T une copie de V, n la valeur 5, s la valeur 5000. La boucle est un comptage (Séance 3) : c part de 0 et augmente de 1 à chaque case qui vérifie le test. La trace complète suit ; la colonne T de compter, copie de V, n’est pas répétée.

principal compter
Pas Ligne Instruction Pile V a n s c i Test Écrit
1 12 V : tableau[1..5] déntiers – · · · · ·
2 13 V ← [5000, 2000, 5000, 3000, 5000] – 5000 2000 5000 3000 5000
3 14 a ← compter(V, 5, 5000) compter 5000 2000 5000 3000 5000 5 5000
4 3 c ← 0 compter 5000 2000 5000 3000 5000 5 5000 0
5 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 5 5000 0 1 vrai
6 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 5 5000 0 1 vrai
7 6 c ← c + 1 compter 5000 2000 5000 3000 5000 5 5000 1 1
8 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 5 5000 1 2 vrai
9 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 5 5000 1 2 faux
10 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 5 5000 1 3 vrai
11 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 5 5000 1 3 vrai
12 6 c ← c + 1 compter 5000 2000 5000 3000 5000 5 5000 2 3
13 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 5 5000 2 4 vrai
14 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 5 5000 2 4 faux
15 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 5 5000 2 5 vrai
16 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 5 5000 2 5 vrai
17 6 c ← c + 1 compter 5000 2000 5000 3000 5000 5 5000 3 5
18 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 5 5000 3 6 faux
19 9 Retourner c compter 5000 2000 5000 3000 5000 5 5000 3 rend 3
20 14 a ← compter(V, 5, 5000) – 5000 2000 5000 3000 5000 3
21 15 Écrire a, compter(V, 5, 3000) - a compter 5000 2000 5000 3000 5000 3 5 3000
22 3 c ← 0 compter 5000 2000 5000 3000 5000 3 5 3000 0
23 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 3 5 3000 0 1 vrai
24 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 3 5 3000 0 1 vrai
25 6 c ← c + 1 compter 5000 2000 5000 3000 5000 3 5 3000 1 1
26 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 3 5 3000 1 2 vrai
27 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 3 5 3000 1 2 faux
28 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 3 5 3000 1 3 vrai
29 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 3 5 3000 1 3 vrai
30 6 c ← c + 1 compter 5000 2000 5000 3000 5000 3 5 3000 2 3
31 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 3 5 3000 2 4 vrai
32 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 3 5 3000 2 4 vrai
33 6 c ← c + 1 compter 5000 2000 5000 3000 5000 3 5 3000 3 4
34 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 3 5 3000 3 5 vrai
35 5 Si T[i] ≥ s Alors compter 5000 2000 5000 3000 5000 3 5 3000 3 5 vrai
36 6 c ← c + 1 compter 5000 2000 5000 3000 5000 3 5 3000 4 5
37 4 Pour i de 1 à n Faire compter 5000 2000 5000 3000 5000 3 5 3000 4 6 faux
38 9 Retourner c compter 5000 2000 5000 3000 5000 3 5 3000 4 rend 4
39 15 Écrire a, compter(V, 5, 3000) - a – 5000 2000 5000 3000 5000 3 3 1
\(i\) T[i] T[i] \(\geq\) s c après le tour
1 5000 vrai 1
2 2000 faux 1
3 5000 vrai 2
4 3000 faux 2
5 5000 vrai 3

Le premier appel rend 3 (pas 19), et a reçoit 3 (pas 20).

(b) La ligne 15 appelle compter(V, 5, 3000) dans l’expression compter(V, 5, 3000) - a : un nouveau cadre est créé (pas 21), où s vaut 3000. Quatre versements valent au moins 3000 F ; l’appel rend 4 (pas 38), et la ligne écrit 3 1 : un seul membre a versé au moins 3000 F sans atteindre 5000 F.

(c) Deux cadres d’appel, un par appel (pas 3 et 21) ; chacun est retiré par Retourner, et la ligne 9 s’exécute 2 fois (pas 19 et 38). Le second cadre ne garde rien du premier : c y repart de 0 (pas 22).

(d) Les formels sont T, n et s, les noms de l’en-tête ; les effectifs de l’appel de la ligne 15 sont V, 5 et 3000. Passé par valeur, T est une copie de V : la fonction ne peut pas modifier les versements.

Conclusion. Une fonction écrite une fois sert pour plusieurs seuils : chaque appel a son cadre, ses copies, sa valeur rendue.

AvertissementErreur fréquente

Croire que c existe dans le programme principal après l’appel, et écrire Écrire c : c est locale à compter. Autre erreur répandue : inverser l’ordre des effectifs, compter(V, 5000, 5), qui donne \(n=5000\) pour un tableau de 5 cases : appel incorrect.

Exercice 2 : valeur ou entrée-sortie

La caisse d’un GIE de femmes de Kaolack reçoit les parts de ses membres. La procédure verser ajoute une part à un solde.

Procédure verser(E/S solde : entier,
    m : entier)
  solde ← solde + m
  m ← 0
FinProcédure
Début
  caisse ← 20000
  part ← 5000
  verser(caisse, part)
  verser(caisse, part)
  Écrire caisse, part
Fin
  1. Pour chacun des deux appels, relever solde après la ligne 3, m après la ligne 4, puis caisse et part après le retour.
  2. Qu’écrit la ligne 11 ?
  3. Qu’écrit l’algorithme si l’en-tête ne porte pas E/S devant solde ?
  4. Qu’écrit l’algorithme si l’en-tête porte E/S devant solde et devant m ?
AstuceCorrection

(a) Règle appliquée. solde est passé en E/S : il désigne caisse, et la ligne 3 écrit dans caisse. m est passé par valeur : c’est une copie de part, et la ligne 4 ne modifie que la copie.

principal verser
Pas Ligne Instruction Pile caisse part solde m Test Écrit
1 7 caisse ← 20000 – 20000
2 8 part ← 5000 – 20000 5000
3 9 verser(caisse, part) verser 20000 5000 \(\rightarrow\)caisse 5000
4 3 solde ← solde + m verser 25000 5000 \(\rightarrow\)caisse 5000
5 4 m ← 0 verser 25000 5000 \(\rightarrow\)caisse 0
6 5 FinProcédure verser 25000 5000 \(\rightarrow\)caisse 0
7 10 verser(caisse, part) verser 25000 5000 \(\rightarrow\)caisse 5000
8 3 solde ← solde + m verser 30000 5000 \(\rightarrow\)caisse 5000
9 4 m ← 0 verser 30000 5000 \(\rightarrow\)caisse 0
10 5 FinProcédure verser 30000 5000 \(\rightarrow\)caisse 0
11 11 Écrire caisse, part – 30000 5000 30000 5000
appel solde après l. 3 m après l. 4 caisse après le retour part après le retour
1 (ligne 9) 25000 0 25000 5000
2 (ligne 10) 30000 0 30000 5000

solde et caisse sont une seule et même variable : le gras des pas 4 et 8 est dans la colonne caisse. Le m \(\leftarrow\) 0 des pas 5 et 9 met la copie à 0, et le cadre qui la contient est retiré aux pas 6 et 10.

(b) La ligne 11 écrit 30000 5000 : deux parts de 5000 F ont été versées, et part n’a pas changé.

(c) Sans E/S, solde est une copie de caisse : chaque appel augmente la copie, puis la perd.

principal verser
Pas Ligne Instruction Pile caisse part solde m Test Écrit
1 7 caisse ← 20000 – 20000
2 8 part ← 5000 – 20000 5000
3 9 verser(caisse, part) verser 20000 5000 20000 5000
4 3 solde ← solde + m verser 20000 5000 25000 5000
5 4 m ← 0 verser 20000 5000 25000 0
6 5 FinProcédure verser 20000 5000 25000 0
7 10 verser(caisse, part) verser 20000 5000 20000 5000
8 3 solde ← solde + m verser 20000 5000 25000 5000
9 4 m ← 0 verser 20000 5000 25000 0
10 5 FinProcédure verser 20000 5000 25000 0
11 11 Écrire caisse, part – 20000 5000 20000 5000

L’algorithme écrit 20000 5000 : la caisse n’a rien reçu, sans aucun message.

(d) Avec E/S devant m, la ligne 4 écrit dans part : le premier appel verse 5000, puis met part à 0, et le second verse 0.

principal verser
Pas Ligne Instruction Pile caisse part solde m Test Écrit
1 7 caisse ← 20000 – 20000
2 8 part ← 5000 – 20000 5000
3 9 verser(caisse, part) verser 20000 5000 \(\rightarrow\)caisse \(\rightarrow\)part
4 3 solde ← solde + m verser 25000 5000 \(\rightarrow\)caisse \(\rightarrow\)part
5 4 m ← 0 verser 25000 0 \(\rightarrow\)caisse \(\rightarrow\)part
6 5 FinProcédure verser 25000 0 \(\rightarrow\)caisse \(\rightarrow\)part
7 10 verser(caisse, part) verser 25000 0 \(\rightarrow\)caisse \(\rightarrow\)part
8 3 solde ← solde + m verser 25000 0 \(\rightarrow\)caisse \(\rightarrow\)part
9 4 m ← 0 verser 25000 0 \(\rightarrow\)caisse \(\rightarrow\)part
10 5 FinProcédure verser 25000 0 \(\rightarrow\)caisse \(\rightarrow\)part
11 11 Écrire caisse, part – 25000 0 25000 0

L’algorithme écrit 25000 0.

Conclusion. La mention E/S se met devant les seuls paramètres que la procédure doit modifier pour l’appelant : ici solde, et pas m.

AvertissementErreur fréquente

Lire m \(\leftarrow\) 0 comme une remise à zéro de part : sans E/S, l’affectation ne touche que la copie. Pour savoir ce qu’une procédure peut modifier chez l’appelant, il faut lire son en-tête, pas son corps.

Exercice 3 : pile des appels et erreurs

Fonction carre(x : entier) : entier
  Retourner x × x
FinFonction
Fonction somCarres(a : entier,
    b : entier) : entier
  s ← carre(a) + carre(b)
  Retourner s
FinFonction
Début
  x ← 3
  r ← somCarres(x, x + 1)
  Écrire x, r
Fin
  1. Donner la pile des appels, avec les variables de chaque cadre, à chaque exécution de la ligne 2.
  2. Qu’écrit la ligne 12 ? Pourquoi x vaut-il encore 3, alors que carre a un paramètre x qui reçoit 4 ?
  3. La ligne 2 devient y \(\leftarrow\) x \(\times\) x. Que se passe-t-il ?
  4. On rétablit la ligne 2, et la ligne 12 devient Écrire x, s. Que se passe-t-il ?
AstuceCorrection

(a) Règle appliquée. Chaque appel empile un cadre au sommet ; un Retourner retire le cadre du sommet. La ligne 6 contient deux appels de carre, exécutés l’un après l’autre, de gauche à droite : le second commence quand le premier a rendu sa valeur.

principal somCarres carre
Pas Ligne Instruction Pile x r a b s x Test Écrit
1 10 x ← 3 – 3
2 11 r ← somCarres(x, x + 1) somCarres 3 3 4
3 6 s ← carre(a) + carre(b) somCarres, carre 3 3 4 3
4 2 Retourner x × x somCarres, carre 3 3 4 3 rend 9
5 6 s ← carre(a) + carre(b) somCarres, carre 3 3 4 4
6 2 Retourner x × x somCarres, carre 3 3 4 4 rend 16
7 6 s ← carre(a) + carre(b) somCarres 3 3 4 25
8 7 Retourner s somCarres 3 3 4 25 rend 25
9 11 r ← somCarres(x, x + 1) – 3 25
10 12 Écrire x, r – 3 25 3 25

Pas 4 : premier passage par la ligne 2.

Pas 6 : second passage par la ligne 2.

passage par la ligne 2 cadre 1 (bas) cadre 2 cadre 3 (sommet)
1 (pas 4) principal : \(x=3\) somCarres : \(a=3\), \(b=4\) carre : \(x=3\)
2 (pas 6) principal : \(x=3\) somCarres : \(a=3\), \(b=4\) carre : \(x=4\)

Le cadre de carre du premier appel est retiré au pas 4 ; celui du second appel est un cadre nouveau, créé au pas 5.

(b) La ligne 12 écrit 3 25 : somCarres rend \(9+16=25\) (pas 8). Le x de carre est une variable locale de carre, dans son cadre ; celui du programme principal, dans le cadre du bas, n’a jamais été écrit après le pas 1.

(c) Avec y \(\leftarrow\) x \(\times\) x, la fonction calcule 9 mais ne le rend pas : le premier appel de carre atteint FinFonction, ligne 3, sans Retourner, et l’exécution s’arrête.

principal somCarres carre
Pas Ligne Instruction Pile x a b x y Test Écrit
1 10 x ← 3 – 3
2 11 r ← somCarres(x, x + 1) somCarres 3 3 4
3 6 s ← carre(a) + carre(b) somCarres, carre 3 3 4 3
4 2 y ← x × x somCarres, carre 3 3 4 3 9
5 3 FinFonction somCarres, carre 3 3 4 3 9 erreur arrêt : pas de Retourner

Rien n’est écrit : l’arrêt survient avant la ligne 12.

(d) s est une variable locale de somCarres ; son cadre a été retiré au pas 8. Au pas 10, la ligne 12 demande s dans le cadre du programme principal, qui ne la connaît pas : arrêt.

principal somCarres carre
Pas Ligne Instruction Pile x r a b s x Test Écrit
1 10 x ← 3 – 3
2 11 r ← somCarres(x, x + 1) somCarres 3 3 4
3 6 s ← carre(a) + carre(b) somCarres, carre 3 3 4 3
4 2 Retourner x × x somCarres, carre 3 3 4 3 rend 9
5 6 s ← carre(a) + carre(b) somCarres, carre 3 3 4 4
6 2 Retourner x × x somCarres, carre 3 3 4 4 rend 16
7 6 s ← carre(a) + carre(b) somCarres 3 3 4 25
8 7 Retourner s somCarres 3 3 4 25 rend 25
9 11 r ← somCarres(x, x + 1) – 3 25
10 12 Écrire x, s – 3 25 erreur arrêt : s inconnue

La valeur voulue, 25, est dans r.

Conclusion. Une pile se lit de bas en haut : chaque cadre attend la valeur de celui qui est au-dessus de lui, et seules les variables du cadre actif sont accessibles.

AvertissementErreur fréquente

Dessiner un seul cadre carre pour les deux appels, ou garder le premier cadre jusqu’à la fin : chaque appel a son cadre, retiré à son retour. Autre erreur répandue : penser que le x de carre est celui du programme principal parce qu’il porte le même nom.

À retenir

Rend Appel Paramètres
fonction une valeur, par Retourner dans une expression : z \(\leftarrow\) f(x) par valeur (copies)
procédure rien instruction seule : p(x, y) par valeur, ou E/S (la variable elle-même)
tableau par valeur copié case par case (choix du cours) ; le sous-programme lit et modifie sa copie
tableau en E/S non copié ; la procédure modifie les cases du tableau effectif
  • Un appel évalue les effectifs, empile un cadre d’appel et y copie les valeurs dans les formels ; Retourner ou FinProcédure retire le cadre.
  • Retourner termine l’appel, même au milieu d’une boucle ; une fonction doit en exécuter un sur chacun de ses chemins.
  • Une variable locale n’existe que dans son cadre d’appel : deux variables de même nom dans deux fonctions sont différentes.
  • Trois erreurs : Retourner oublié, paramètre par valeur modifié pour changer l’appelant, variable locale lue hors de sa fonction.

Synthèse du cours

Les six séances du cours se complètent : la Séance 0 définit l’algorithme et son exécution à la main ; la Séance 1, les variables, l’affectation, Lire, Écrire et la trace d’exécution ; la Séance 2, les conditions (Si, Sinon, SinonSi, Selon, ET, OU, NON) ; la Séance 3, les boucles, le compteur et l’accumulateur ; la Séance 4, les tableaux et leurs parcours ; la présente séance, les fonctions et les procédures, qui donnent un nom à ces traitements. Un algorithme du cours se construit ainsi en traitements nommés, faits de variables, de conditions, de boucles et de tableaux, et se vérifie par une trace sur un cas ordinaire et sur un cas limite.

Références

  • Cormen — Algorithms Unlocked, MIT Press, 2013 (ch. 1, « What Are Algorithms and Why Should You Care? », et ch. 2, « How to Describe and Evaluate Computer Algorithms » : procédures et paramètres en pseudo-code).
  • Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms, 4e éd., MIT Press, 2022 (ch. 2, « Getting Started », § 2.1 : conventions du pseudo-code, paramètres passés par valeur).
  • Bhargava — Grokking Algorithms, 2e éd., Manning, 2024 (ch. 3, « Recursion » : la pile des appels).
  • Notes de cours en ligne : CS50 (Harvard), 6.100A (MIT), CS106A (Stanford), séances sur les fonctions.

Pour cette séance

Les slides

À lire en ligne

Retour au sommet