UTILISATION DES FONCTIONS ET DES PROCEDURES

## Objectifs et prérequis **Objectifs** : À la fin de ce chapitre, l’élève sera capable de 1. Définir précisément ce qu’est une fonction et une procédure dans un algorithme. 2. Écrire une fonction ou une procédure en respectant la syntaxe du pseudo‑code officiel (MINESEC/IGE). 3. Identifier et justifier le mode de passage des paramètres (valeur, résultat, valeur‑résultat, référence) adapté à un problème donné. 4. Tracer l’exécution d’un algorithme qui fait appel à plusieurs fonctions et procédures, en suivant la pile d’appels et les modifications des variables. 5. Déboguer un algorithme modulaire en repérant les erreurs liées au passage de paramètres ou à la mauvaise utilisation d’une valeur de retour. **Prérequis** : L’élève doit déjà maîtriser * Les notions de variable, d’affectation et de type de donnée (entier, réel, booléen, chaîne). * Les structures de contrôle séquentielle, alternative (`si…alors…sinon…finsi`) et répétitive (`tant que…faire…fin tant que`, `pour…de…à…faire…fin pour`). * La manipulation simple de tableaux unidimensionnels (lecture, écriture, parcours). * La lecture et l’écriture de pseudo‑code de base (début…fin, instruction, commentaire). --- ## Introduction contextualisée Dans la résolution de problèmes informatiques, il est fréquent de rencontrer des sous‑tâches qui se répètent ou qui peuvent être traitées indépendamment du reste du programme. Plutôt que de dupliquer le même bloc d’instructions à chaque occurrence, on regroupe ces instructions dans un **sous‑algorithme** que l’on peut appeler autant de fois que nécessaire. Cette approche, appelée **programmation modulaire**, présente plusieurs avantages : * **Lisibilité** : le programme principal devient plus court et chaque sous‑algorithme porte un nom explicite qui décrit son rôle. * **Réutilisabilité** : une même fonction ou procédure peut être utilisée dans différents programmes sans réécriture. * **Maintenabilité** : une modification apportée au sous‑algorithme se répercute automatiquement partout où il est appelé. * **Testabilité** : on peut tester chaque sous‑algorithme isolément avant de l’intégrer dans le programme principal. Dans le programme officiel de la série C, D, E de la Première, les sous‑algorithmes se déclinent en deux catégories : les **fonctions**, qui produisent une valeur de retour, et les **procédures**, qui n’en produisent pas mais peuvent modifier leurs paramètres. Le chapitre suivant détaille ces deux notions, les différents modes de passage des paramètres qui régissent la façon dont les données sont échangées entre l’appelant et le sous‑algorithme, et enfin la manière dont l’ordinateur exécute réellement un algorithme qui fait appel à plusieurs fonctions et procédures. --- ## I. Leçon 6 : Fonctions et procédures ### 1. Définition d’une fonction > **Une fonction est un sous‑algorithme qui, après son exécution, retourne une valeur au point d’appel.** La valeur retournée peut être de n’importe quel type autorisé par le langage (entier, réel, booléen, chaîne, tableau, etc.). En pseudo‑code officiel, la syntaxe d’une fonction est la suivante : ``` fonction nom_fonction ( liste_de_paramètres ) : type_retour début // instructions du corps retourner expression fin ``` * `nom_fonction` : identificateur respectant les règles de nommage (lettre suivie de lettres, chiffres ou souligné, pas de caractère spécial). * `liste_de_paramètres` : éventuellement vide ; chaque paramètre possède un nom et un type. * `type_retour` : type de la valeur qui sera retournée par l’instruction `retourner`. * Le corps peut contenir des affectations, des structures de contrôle, des appels à d’autres sous‑algorithmes, etc. * L’instruction `retourner` interrompt immédiatement l’exécution de la fonction et transmet la valeur de l’expression au point d’appel. #### Exemple 1 – Fonction carré ``` fonction carré ( x : entier ) : entier début retourner x * x fin ``` *Appel* : `y ← carré(5)` *Exécution* : le paramètre `x` reçoit la valeur 5, le corps calcule `5 * 5 = 25`, l’instruction `retourner 25` renvoie 25, puis `y` reçoit 25. #### Exemple 2 – Fonction valeur absolue ``` fonction abs ( r : réel ) : réel début si r < 0 alors retourner -r sinon retourner r finsi fin ``` *Appel* : `z ← abs(-3.7)` *Exécution* : `r` vaut -3.7, la condition `r < 0` est vraie, on retourne `-(-3.7) = 3.7`. ### 2. Définition d’une procédure > **Une procédure est un sous‑algorithme qui n’émet aucune valeur de retour mais peut modifier les variables qui lui sont passées en paramètres.** Sa syntaxe est similaire à celle d’une fonction, sauf qu’il n’y a pas de type de retour et pas d’instruction `retourner` (ou bien on utilise `retourner` sans valeur, ce qui revient à terminer simplement la procédure). ``` procedure nom_procedure ( liste_de_paramètres ) début // instructions du corps fin ``` * Une procédure peut contenir des `retourner` uniquement pour sortir prématurément (équivalent à un `break` dans une boucle). * Toute modification d’un paramètre passé par référence ou valeur‑résultat sera visible après l’appel. #### Exemple 3 – Procedure d’échange (swap) ``` procedure échange ( a : entier, b : entier ) début temp ← a a ← b b ← temp fin ``` *Remarque* : Dans cette version, les paramètres sont passés **par valeur** ; donc l’échange n’affecte pas les variables réelles appelantes. Nous verrons plus loin comment obtenir un échange effectif en utilisant le mode référence ou valeur‑résultat. #### Exemple 4 – Procedure de remplissage d’un tableau ``` procedure remplir ( T : tableau[1..n] de entier, val : entier ) début pour i de 1 à n faire T[i] ← val fin pour fin ``` *Appel* : `remplir(T, 0)` met toutes les cases de `T` à zéro. ### 3. Différences essentielles entre fonction et procédure | Critère | Fonction | Procédure | |------------------------|------------------------------------------|-------------------------------------------| | Retour de valeur | Oui, via `retourner expression` | Non (pas de valeur de retour) | | Modification des paramètres | Possible seulement si le paramètre est passé par référence ou valeur‑résultat | Possible selon le mode de passage | | Utilisation typique | Calcul d’une valeur (somme, factorielle, etc.) | Action (affichage, tri, échange, mise à jour) | | Appel dans une expression | `y ← f(x)` | `p(x, y)` (instruction autonome) | > **À retenir** : Une fonction doit toujours contenir au moins une instruction `retourner` qui fournit sa valeur de retour ; une procédure ne possède pas de valeur de retour, mais elle peut terminer prématurément avec un `retourner` sans expression. ### 4. Démonstration : propriété de pureté d’une fonction passée par valeur *Proposition* : Si tous les paramètres d’une fonction sont passés **par valeur**, alors l’exécution de la fonction ne modifie aucune variable globale ni aucun argument de l’appelant. *Preuve* : 1. Lors de l’appel, chaque argument est copié dans une nouvelle variable locale du sous‑algorithme (la pile d’appel reçoit une copie). 2. Le corps de la fonction ne peut accéder qu’à ces copies ; toute affectation modifie uniquement la copie locale. 3. À la fin de la fonction, seules les valeurs de retour sont transmises ; les copies locales sont détruites lorsqu’on revient à l’appelant. 4. Donc aucune variable extérieure n’a été altérée. ∎ Cet argument justifie pourquoi, pour obtenir un effet de bord (modification d’une variable extérieure), il faut recourir à un mode de passage autre que la valeur pure. ### 5. Exemple complet : fonction factorielle récursive ``` fonction factorielle ( n : entier ) : entier début si n = 0 alors retourner 1 sinon retourner n * factorielle(n-1) finsi fin ``` *Trace* pour `factorielle(3)` : | Appel | n | Retour attendu | |---------------------|---|----------------| | factorielle(3) | 3 | 3 * factorielle(2) | | factorielle(2) | 2 | 2 * factorielle(1) | | factorielle(1) | 1 | 1 * factorielle(0) | | factorielle(0) | 0 | 1 (cas de base) | | Retour factorielle(1) | | 1 * 1 = 1 | | Retour factorielle(2) | | 2 * 1 = 2 | | Retour factorielle(3) | | 3 * 2 = 6 | Résultat final : 6. --- ## II. Leçon 7 : Modes de passage des paramètres d’un sous algorithme Lorsqu’un sous‑algorithme est appelé, les valeurs réelles (les arguments) sont associées aux paramètres formels selon un **mode de passage**. Quatre modes sont définis dans le programme officiel : 1. **Valeur** (ou *passage par valeur*) 2. **Résultat** (ou *passage par résultat*) 3. **Valeur‑résultat** (ou *passage par valeur‑résultat*) 4. **Référence** (ou *passage par référence*) Chaque mode possède des propriétés distinctes concernant l’initialisation du paramètre, la possibilité de le modifier à l’intérieur du sous‑algorithme, et la façon dont la valeur finale est restituée à l’appelant. ### 1. Mode valeur > **Dans le mode valeur, le paramètre reçoit une copie de la valeur de l’argument au moment de l’appel ; toute modification du paramètre n’affecte pas l’argument.** *Initialisation* : copie de l’argument. *Modification* : autorisée, mais locale. *Restitution* : aucune valeur n’est renvoyée à l’appelant (le paramètre est simplement abandonné à la fin du sous‑algorithme). #### Exemple 5 – Fonction qui incrémente son paramètre (mode valeur) ``` fonction incr ( x : entier ) : entier début retourner x + 1 fin ``` *Appel* : `a ← 5 ; b ← incr(a)` *Trace* : - Au début de `incr`, `x` reçoit la copie de `a` (5). - `x` n’est pas modifié (on ne fait que lire). - Retourne `5+1 = 6`. - Après l’appel, `a` vaut toujours 5. > **À retenir** : En mode valeur, le sous‑algorithme ne peut pas produire d’effet de bord sur ses paramètres. ### 2. Mode résultat > **Dans le mode résultat, le paramètre est utilisé uniquement pour retourner une valeur ; la valeur initiale de l’argument est ignorée, et à la fin du sous‑algorithme l’argument reçoit la valeur calculée.** *Initialisation* : l’argument n’est pas copié ; le paramètre commence indéfini (ou avec une valeur indéterminée). *Modification* : obligatoire ; le sous‑algorithme doit assigner une valeur au paramètre avant de se terminer. *Restitution* : à la fin, la valeur du paramètre est recopiée dans l’argument. #### Exemple 6 – Procedure qui retourne une constante (mode résultat) ``` procedure retourne_cinq ( x : entier ) // mode résultat début x ← 5 fin ``` *Appel* : `y ← 7 ; retourne_cinq(y)` *Trace* : - Au début, le paramètre `x` reçoit aucune copie de `y` (il est indéfini). - L’instruction `x ← 5` affecte la valeur 5 au paramètre. - Retour : l’argument `y` reçoit 5. - Après l’appel, `y = 5` (la valeur initiale 7 est perdue). > **À retenir** : En mode résultat, l’argument sert uniquement de réceptacle de sortie ; sa valeur d’entrée est inutile. ### 3. Mode valeur‑résultat > **Dans le mode valeur‑résultat, le paramètre reçoit initialement une copie de la valeur de l’argument (comme en mode valeur), peut être modifié librement pendant l’exécution, et à la fin du sous‑algorithme la valeur finale du paramètre est recopiée dans l’argument.** *Initialisation* : copie de l’argument. *Modification* : autorisée, travaille sur la copie. *Restitution* : la copie modifiée est renvoyée à l’argument. #### Exemple 7 – Procedure qui incrémente son paramètre (mode valeur‑résultat) ``` procedure incr_vr ( x : entier ) // mode valeur‑résultat début x ← x + 1 fin ``` *Appel* : `a ← 5 ; incr_vr(a)` *Trace* : - Au début de l’appel, `x` reçoit la copie de `a` → `x = 5`. - `x ← x + 1` → `x = 6`. - Fin du sous‑algorithme : la valeur finale de `x` (6) est recopiée dans l’argument `a`. - Après l’appel, `a = 6`. > **À retenir** : Le mode valeur‑résultat combine les propriétés du mode valeur (isolation pendant l’exécution) et du mode résultat (restitution de la valeur modifiée). ### 4. Mode référence > **Dans le mode référence, le paramètre est un alias (un autre nom) de l’argument ; toute lecture ou écriture sur le paramètre affecte directement l’argument.** *Initialisation* : aucun copie ; le paramètre pointe vers la même localisation mémoire que l’argument. *Modification* : autorisée et immédiatement visible. *Restitution* : inutile, car l’argument est déjà modifié en temps réel. #### Exemple 8 – Procedure d’échange efficace (mode référence) ``` procedure échange_ref ( a : entier, b : entier ) // mode référence début temp ← a a ← b b ← temp fin ``` *Appel* : `x ← 7 ; y ← 3 ; échange_ref(x, y)` *Trace* : - Au début, les paramètres `a` et `b` sont des alias de `x` et `y` respectivement. - `temp ← a` → `temp = 7`. - `a ← b` → `a` (donc `x`) prend la valeur de `b` (donc `y`) → `x = 3`. - `b ← temp` → `b` (donc `y`) prend la valeur de `temp` → `y = 7`. - Après l’appel, `x = 3` et `y = 7`. > **À retenir** : Le mode référence permet des effets de bord immédiats et est indispensable lorsqu’on veut modifier réellement une variable passée en argument. ### 5. Tableau récapitulatif des propriétés | Mode | Initialisation | Lecture du paramètre | Écriture du paramètre | Restitution à la fin | |-----------------|----------------|----------------------|-----------------------|----------------------| | Valeur | Copie de l’argument | Lecture de la copie | Modification locale | Aucune | | Résultat | Aucun (indéfini) | Lecture interdite avant affectation | Doit être affecté avant fin | Valeur finale copiée | | Valeur‑résultat | Copie de l’argument | Lecture de la copie | Modification de la copie | Copie finale copiée | | Référence | Alias de l’argument | Lecture de l’argument | Écriture sur l’argument | Aucun (déjà modifié) | > **À retenir** : Le choix du mode dépend de l’intention du sous‑algorithme : calcul pur (valeur), retour uniquement (résultat), modification avec retour (valeur‑résultat), ou effet de bord immédiat (référence). ### 6. Démonstration : équivalence entre valeur‑résultat et séquence valeur + résultat *Proposition* : Un appel à une procédure en mode valeur‑résultat produit le même effet que l’enchaînement suivant : (1) passer l’argument en mode valeur à une procédure interne qui travaille sur une copie, (2) puis copier le résultat de la copie vers l’argument en mode résultat. *Preuve* : - Étape 1 (valeur) : la procédure interne reçoit une copie `c` de l’argument `a`. Toutes ses modifications portent sur `c`. - Étape 2 (résultat) : à la fin, la procédure interne affecte `c` à une variable de sortie `r`. Le mode résultat copie alors `r` dans l’argument `a`. - Ainsi, la valeur finale de `a` est exactement la valeur que la procédure interne aurait calculée sur sa copie et restituée. - Donc les deux approches sont équivalentes. ∎ Cette propriété justifie pourquoi certains langages n’offrent que les deux modes valeur et référence, le mode valeur‑résultat étant implémenté par une combinaison des deux. ### 7. Exemple complet illustrant les quatre modes Considérons l’algorithme suivant qui manipule deux variables entières `x` et `y` : ``` algorithme ExempleModes début x ← 10 y ← 20 affichage "Avant appel : x = ", x, ", y = ", y appel1 ( x ) // mode valeur appel2 ( y ) // mode résultat appel3 ( x ) // mode valeur‑résultat appel4 ( x, y ) // mode référence (deux paramètres) affichage "Après appel : x = ", x, ", y = ", y fin procedure appel1 ( p : entier ) // valeur début p ← p + 5 fin procedure appel2 ( p : entier ) // résultat début p ← 100 // valeur constante, l’entrée est ignorée fin procedure appel3 ( p : entier ) // valeur‑résultat début p ← p - 3 fin procedure appel4 ( a : entier, b : entier ) // référence début temp ← a a ← b b ← temp fin ``` *Trace détaillée* : | Étape | x | y | Action | Commentaire | |-------|---|---|--------|-------------| | Init |10 |20 | – | Valeurs initiales | | Après `affichage` |10 |20 | – | Affiche 10,20 | | `appel1(x)` (valeur) |10 |20 | `p` reçoit copie de `x` (=10), `p ← p+5` → `p=15` ; aucune restitution | `x` reste 10 | | `appel2(y)` (résultat) |10 |20 | `p` reçoit aucune copie, on lui affecte `p ← 100` ; restitution → `y=100` | `y` devient 100 | | `appel3(x)` (valeur‑résultat) |10 |100 | `p` reçoit copie de `x` (=10), `p ← p-3` → `p=7` ; restitution → `x=7` | `x` devient 7 | | `appel4(x,y)` (référence) |7 |100 | `a` alias de `x`, `b` alias de `y` ; `temp←a` →7 ; `a←b` → `x=100` ; `b←temp` → `y=7` | `x` et `y` échangés | | Fin |100 |7 | – | Résultat final affiché | Résultat affiché : ``` Avant appel : x = 10 , y = 20 Après appel : x = 100 , y = 7 ``` --- ## III. Leçon 8 : Exécution d’un algorithme intégrant les fonctions et les procédures L’exécution d’un algorithme qui fait appel à des sous‑algorithmes repose sur le principe de **pile d’appels** (ou *call stack*). À chaque appel, l’environnement d’exécution (variables locales, paramètres, adresse de retour) est empilé ; à la fin du sous‑algorithme, l’environnement est dépilé et le contrôle revient à l’appelant. ### 1. Déroulement général d’un appel 1. **Évaluation des arguments** : chaque expression d’argument est évaluée dans l’environnement courant. 2. **Passage des paramètres** : selon le mode déclaré, les valeurs sont copiées, des alias sont créés, ou des préparations de résultat sont faites. 3. **Création de la pile d’appel** : un nouvel cadre (frame) est alloué contenant : * les paramètres (avec leurs valeurs initiales selon le mode), * les variables locales déclarées dans le sous‑algorithme, * l’adresse de retour (point d’exécution à reprendre après le `retourner` ou la fin de la procédure). 4. **Exécution du corps** : les instructions sont exécutées séquentiellement, éventuellement avec des appels imbriqués. 5. **Sortie** : * Si c’est une fonction, l’instruction `retourner expr` est rencontrée ; la valeur de `expr` est enregistrée comme valeur de retour. * Si c’est une procédure, l’exécution atteint la fin du corps (ou un `retourner` sans valeur). 6. **Dépilement** : le cadre est retiré de la pile ; la valeur de retour (le cas échéant) est transmise à l’appelant ; l’exécution reprend à l’adresse de retour. ### 2. Exemple complet : algorithme qui lit un tableau, calcule sa moyenne, puis le trie par sélection Nous allons détailler pas à pas l’exécution de l’algorithme suivant, en montrant la pile d’appels à chaque étape. ``` algorithme MoyenneEtTri début n ← 5 déclarer T[1..n] de entier // lecture du tableau pour i de 1 à n faire lire T[i] fin pour affichage "Tableau lu : " pour i de 1 à n faire affichage T[i], " " fin pour affichage "" // calcul de la moyenne moy ← moyenne(T, n) // appel de fonction affichage "Moyenne = ", moy // tri par sélection tri_selection(T, n) // appel de procédure affichage "Tableau trié : " pour i de 1 à n faire affichage T[i], " " fin pour fin fonction moyenne ( tab : tableau[1..n] de entier, taille : entier ) : réel début somme ← 0 pour i de 1 à taille faire somme ← somme + tab[i] fin pour retourner somme / taille fin procedure tri_selection ( tab : tableau[1..n] de entier, taille : entier ) début pour i de 1 à taille-1 faire min ← i pour j de i+1 à taille faire si tab[j] < tab[min] alors min ← j finsi fin pour // échange des éléments i et min (mode référence) temp ← tab[i] tab[i] ← tab[min] tab[min] ← temp fin pour fin ``` #### Jeu de données d’entrée Supposons que l’utilisateur entre les valeurs suivantes (dans l’ordre) : `8, 3, 5, 9, 2`. #### Trace détaillée Nous allons suivre la pile d’appels à chaque moment significatif. Pour simplifier, nous noterons chaque cadre par son nom et ses variables locales/paramètres. | Étape | Action | Pile d’appels (bas → haut) | État des variables importantes | |-------|--------|----------------------------|--------------------------------| | 1 | Début de `MoyenneEtTri` | `[MoyenneEtTri]` | `n=5`, `T` non encore rempli | | 2 | Boucle de lecture (i=1) | `[MoyenneEtTri]` | `T[1]=8` | | 3 | i=2 | `[MoyenneEtTri]` | `T[2]=3` | | 4 | i=3 | `[MoyenneEtTri]` | `T[3]=5` | | 5 | i=4 | `[MoyenneEtTri]` | `T[4]=9` | | 6 | i=5 | `[MoyenneEtTri]` | `T[5]=2` | | 7 | Affichage du tableau lu | `[MoyenneEtTri]` | `T = [8,3,5,9,2]` | | 8 | Appel `moyenne(T, n)` | `[MoyenneEtTri]` → `[moyenne]` | Paramètres : `tab` (référence au tableau `T`), `taille=5` (valeur) | | 9 | Dans `moyenne` – initialisation `somme←0` | `[MoyenneEtTri]` → `[moyenne]` | `somme=0` | |10 | Boucle sommation i=1..5 (détaillons) | | | |10a| i=1 : `somme←0+T[1]=8` | | `somme=8` | |10b| i=2 : `somme←8+T[2]=3` | | `somme=11` | |10c| i=3 : `somme←11+T[3]=5` | | `somme=16` | |10d| i=4 : `somme←16+T[4]=9` | | `somme=25` | |10e| i=5 : `somme←25+T[5]=2` | | `somme=27` | |11 | Retour `retourner somme / taille` → `27/5 = 5.4` | `[MoyenneEtTri]` ← `[moyenne]` (dépilement) | Retour valeur 5.4 reçue dans `moy` | |12 | Après retour, affichage moyenne | `[MoyenneEtTri]` | `moy = 5.4` | |13 | Appel `tri_selection(T, n)` | `[MoyenneEtTri]` → `[tri_selection]` | Paramètres : `tab` (référence à `T`), `taille=5` (valeur) | |14 | Dans `tri_selection` – boucle extérieure i=1..4 (détaillons) | | | |14a| i=1 : `min←1` ; boucle intérieure j=2..5 : <br> - j=2 : `T[2]=3 < T[1]=8` → `min=2` <br> - j=3 : `T[3]=5 < T[2]=3` ? non <br> - j=4 : `T[4]=9 < 3` ? non <br> - j=5 : `T[5]=2 < 3` → `min=5` <br> Échange `T[1]` ↔ `T[5]` : `T` devient `[2,3,5,9,8]` | | | |14b| i=2 : `min←2` ; j=3..5 : <br> - j=3 : `5<3` ? non <br> - j=4 : `9<3` ? non <br> - j=5 : `8<3` ? non → `min=2` (pas d’échange) | | | |14c| i=3 : `min←3` ; j=4..5 : <br> - j=4 : `9<5` ? non <br> - j=5 : `8<5` ? non → `min=3` (pas d’échange) | | | |14d| i=4 : `min←4` ; j=5 : `8<9` → `min=5` ; échange `T[4]` ↔ `T[5]` : `T` devient `[2,3,5,8,9]` | | | |15 | Fin de `tri_selection` (pas de retour) | `[MoyenneEtTri]` ← `[tri_selection]` (dépilement) | Tableau maintenant trié | |16 | Affichage du tableau trié | `[MoyenneEtTri]` | `T = [2,3,5,8,9]` | |17 | Fin de `MoyenneEtTri` | pile vide | Programme terminé | **Observations** : * La fonction `moyenne` a été appelée en mode **valeur** pour le paramètre `taille` (simple copie) et en mode **référence** pour le paramètre `tab` (puisque nous voulons lire les éléments du tableau sans le copier entièrement). Dans le pseudo‑code officiel, on ne précise pas toujours le mode pour les tableaux ; on sous‑entend que le tableau est passé par référence afin d’éviter une copie coûteuse. * La procédure `tri_selection` utilise le mode **référence** pour le tableau afin de pouvoir le modifier directement ; le paramètre `taille` est passé par valeur car il ne sert qu’à borner les boucles. * À chaque appel, une nouvelle frame est créée ; les variables locales (`somme`, `i`, `min`, `j`, `temp`) sont isolées et disparaissent à la fin du sous‑algorithme. > **À retenir** : L’exécution d’un algorithme modulaire suit une discipline stricte de pile d’appels ; comprendre cette mécanique permet de prédire l’état des variables à tout moment et de déboguer efficacement les erreurs de portée ou de passage de paramètres. ### 3. Exemple avec récursion (fonction factorielle) et trace de pile Rappelons la fonction factorielle définie précédemment : ``` fonction factorielle ( n : entier ) : entier début si n = 0 alors retourner 1 sinon retourner n * factorielle(n-1) finsi fin ``` Trace de l’appel `factorielle(4)` : | Niveau de pile | n | Action | Retour attendu | |----------------|---|--------|----------------| | 0 (appel initial) | 4 | `si 4=0` non → appeler `factorielle(3)` | `4 * résultat(3)` | | 1 | 3 | appeler `factorielle(2)` | `3 * résultat(2)` | | 2 | 2 | appeler `factorielle(1)` | `2 * résultat(1)` | | 3 | 1 | appeler `factorielle(0)` | `1 * résultat(0)` | | 4 | 0 | `si 0=0` oui → retourner 1 | 1 | | Retour niveau 3 | | `1 * 1 = 1` | 1 | | Retour niveau 2 | | `2 * 1 = 2` | 2 | | Retour niveau 1 | | `3 * 2 = 6` | 6 | | Retour niveau 0 | | `4 * 6 = 24` | 24 | À chaque appel récursif, un nouveau cadre est empilé avec sa propre copie de `n`. Lorsque le cas de base est atteint, les cadres sont dépilés successivement, chaque niveau effectuant la multiplication avec la valeur retournée du niveau inférieur. > **À retenir** : La récursion consomme de la mémoire proportionnelle à la profondeur de la récursion (ici O(n)). Une profondeur trop grande peut provoquer un dépassement de pile (stack overflow). ### 4. Exemple d’algorithme mêlant fonctions, procédures et différents modes de passage Considérons l’algorithme suivant qui calcule la norme euclidienne d’un vecteur et qui, en fonction d’un seuil, effectue ou non une normalisation du vecteur. ``` algorithme NormeEtNormalisation début déclarer V[1..3] de réel lire V[1], V[2], V[3] // saisie des composantes seuil ← 10.0 n ← norme(V, 3) // appel de fonction affichage "Norme = ", n si n > seuil alors normaliser(V, 3) // appel de procédure (modifie V) affichage "Vecteur normalisé : " pour i de 1 à 3 faire affichage V[i], " " fin pour sinon affichage "Norme inférieure au seuil, pas de normalisation." finsi fin fonction norme ( v : tableau[1..3] de réel, dim : entier ) : réel début somme ← 0.0 pour i de 1 à dim faire somme ← somme + v[i] * v[i] fin pour retourner racine(somme) // on suppose la fonction racine disponible fin procedure normaliser ( v : tableau[1..3] de réel, dim : entier ) début n ← norme(v, dim) // appel imbriqué de fonction pour i de 1 à dim faire v[i] ← v[i] / n fin pour fin ``` **Jeu de données** : `V = [6.0, 8.0, 0.0]` *Calcul de la norme* : `somme = 6² + 8² + 0² = 36 + 64 = 100` → `racine(100) = 10.0` Puisque `n = 10.0` est égal au seuil (on utilise `>`, donc pas de normalisation). Si on changeait le seuil à `9.0`, la condition serait vraie et on entrerait dans la procédure `normaliser`. **Trace de la normalisation (seuil = 9.0)** : 1. Appel `norme(V,3)` → même calcul que précédemment → retourne `10.0`. 2. Dans `normaliser` : * `n ← norme(V,3)` → nouvel appel à `norme` (même résultat 10.0). * Boucle : - i=1 : `V[1] ← 6.0 / 10.0 = 0.6` - i=2 : `V[2] ← 8.0 / 10.0 = 0.8` - i=3 : `V[3] ← 0.0 / 10.0 = 0.0` 3. Après la procédure, `V = [0.6, 0.8, 0.0]` dont la norme est bien 1.0. Cet exemple montre : * Une **fonction** (`norme`) utilisée deux fois, une fois dans l’algorithme principal, une fois dans la procédure. * Une **procédure** (`normaliser`) qui modifie son argument (tableau passé par référence). * Un **appel imbriqué** de fonction à l’intérieur d’une procédure. * Le passage du paramètre `dim` par valeur (simple copie). * Le passage du tableau `v` par référence (afin de pouvoir le lire et le modifier). > **À retenir** : La combinaison de fonctions et procédures permet de décomposer un problème en sous‑tâches réutilisables, tout en maîtrisant soigneusement quelles données sont seulement lues, lesquelles sont modifiées, et lesquelles sont seulement retournées. --- ## Synthèse du chapitre - **Fonction** : sous‑algorithme qui retourne une valeur (`retourner expression`). - **Procédure** : sous‑algorithme qui ne retourne pas de valeur mais peut modifier ses paramètres. - **Mode valeur** : copie de l’argument ; aucune modification visible à l’extérieur. - **Mode résultat** : l’argument sert uniquement à recevoir une valeur de sortie ; sa valeur d’entrée est ignorée. - **Mode valeur‑résultat** : copie de l’argument, modification possible sur la copie, restitution de la copie modifiée à la fin. - **Mode référence** : alias de l’argument ; lecture/écriture affectent directement l’argument. - **Exécution** : chaque appel crée une frame sur la pile d’appels contenant paramètres (selon le mode), variables locales et adresse de retour ; le retour dépile la frame et transmet éventuellement une valeur de retour. - **Récursivité** : chaque appel récursif ajoute une frame ; la profondeur de récursion détermine la consommation de pile. - **Tableaux** : généralement passés par référence pour éviter la copie coûteuse ; les dimensions sont passées par valeur. - **Bonnes pratiques** : choisir le mode de passage adapté à l’intention (calcul pur → valeur, retour uniquement → résultat, modification avec retour → valeur‑résultat, effet de bord immédiat → référence). --- ## Glossaire | Terme | Définition | |-------|------------| | Fonction | Sous‑algorithme qui retourne une valeur au moyen de l’instruction `retourner`. | | Procédure | Sous‑algorithme qui ne retourne pas de valeur mais peut modifier ses paramètres. | | Paramètre formel | Variable déclarée dans l’en-tête d’un sous‑algorithme qui représente l’argument reçu lors de l’appel. | | Argument | Expression ou variable fournie lors de l’appel d’un sous‑algorithme. | | Mode valeur | Le paramètre reçoit une copie de la valeur de l’argument ; modifications locales n’affectent pas l’argument. | | Mode résultat | Le paramètre est utilisé uniquement pour retourner une valeur ; la valeur d’entrée de l’argument est ignorée. | | Mode valeur‑résultat | Le paramètre reçoit initialement une copie de l’argument, peut être modifié, et à la fin la copie modifiée est recopiée dans l’argument. | | Mode référence | Le paramètre est un alias de l’argument ; toute lecture/écriture affecte directement l’argument. | | Pile d’appels (call stack) | Structure de données qui mémorise les frames d’exécution des sous‑algorithmes actifs lors de l’exécution d’un programme. | | Frame (cadre d’appel) | Bloc mémoire contenant les paramètres, les variables locales et l’adresse de retour d’un appel de sous‑algorithme. | | Récursivité | Technique où un sous‑algorithme s’appelle lui-même directement ou indirectement. | | Cas de base | Condition dans une fonction récursive qui arrêtent l’appel récursif et retournent une valeur connue. | | Effet de bord | Modification d’une variable extérieure à un sous‑algorithme (via passage référence ou valeur‑résultat). | | Pureté | Propriété d’une fonction qui ne provoque aucun effet de bord et dont le résultat dépend uniquement de ses arguments. | --- ## Exercices d'application corrigés ### Exercice 1 (niveau facile) **Énoncé** : Écrire une fonction `max2(a,b)` qui retourne le plus grand de deux entiers `a` et `b`. Puis écrire une procédure `afficher_max(a,b)` qui affiche ce maximum sans retourner de valeur. **Corrigé** : ``` fonction max2 ( a : entier, b : entier ) : entier début si a >= b alors retourner a sinon retourner b finsi fin procedure afficher_max ( a : entier, b : entier ) début m ← max2(a,b) // appel de fonction affichage "Le maximum est ", m fin ``` *Explication* : La fonction utilise un test simple et retourne la valeur appropriée. La procédure appelle la fonction, stocke le résultat dans une variable locale `m` puis l’affiche. Aucun paramètre n’est modifié, donc le passage par valeur suffit pour les deux appels. --- ### Exercice 2 (niveau moyen) **Énoncé** : Écrire une procédure `echange_ref(x,y)` qui échange les valeurs de deux variables réelles `x` et `y` en utilisant le mode référence. Puis écrire un petit algorithme qui lit deux réels, les échange grâce à la procédure, et affiche les résultats avant et après l’échange. **Corrigé** : ``` procedure echange_ref ( x : réel, y : réel ) // mode référence début temp ← x x ← y y ← temp fin algorithme TestEchange début lire a, b affichage "Avant échange : a = ", a, ", b = ", b echange_ref(a,b) // appel de procédure (référence) affichage "Après échange : a = ", a, ", b = ", b fin ``` *Explication* : Comme les paramètres sont déclarés en mode référence (dans le contexte du cours on sous‑entend que l’écriture `x : réel` dans l’en-tête de la procédure implique référence lorsqu’on veut modifier l’argument), les échanges effectués sur `x` et `y` modifient directement les variables `a` et `b` de l’appelant. --- ### Exercice 3 (niveau moyen) **Énoncé** : Écrire une fonction `factorielle(n)` qui retourne la factorielle d’un entier non négatif `n` en utilisant la récursivité. Puis écrire un algorithme qui lit un entier `n` (0 ≤ n ≤ 12), appelle la fonction et affiche le résultat. **Corrigé** : ``` fonction factorielle ( n : entier ) : entier début si n = 0 alors retourner 1 sinon retourner n * factorielle(n-1) finsi fin algorithme TestFactorielle début lire n si n < 0 alors affichage "Erreur : n doit être positif ou nul" sinon f ← factorielle(n) affichage n! " = ", f finsi fin ``` *Explication* : La fonction respecte la définition récursive de la factorielle. Le cas de base `n=0` retourne 1. Chaque appel récursif diminue `n` de 1, ce qui garantit la terminaison tant que `n` est non négatif. La restriction `n ≤ 12` évite les débordements d’entier dans la plupart des implémentations scolaires (12! = 479001600 tient dans un entier 32 bits signé). --- ### Exercice 4 (niveau moyen) **Énoncé** : On veut déterminer si un tableau d’entiers `T[1..n]` contient un élément égal à la somme des deux précédents (c’est-à-dire trouver un indice `i ≥ 3` tel que `T[i] = T[i-1] + T[i-2]`). 1. Écrire une fonction `est_somme_precedents(T, n)` qui retourne `Vrai` si une telle propriété existe, sinon `Faux`. 2. Écrire une procédure `afficher_indice(T, n)` qui, si la propriété est vraie, affiche le premier indice `i` où elle est vérifiée ; sinon affiche « Aucun indice trouvé ». 3. Écrire un algorithme principal qui lit `n` (2 ≤ n ≤ 20), puis les `n` éléments du tableau, appelle les deux sous‑algorithmes et affiche les résultats. **Corrigé** : ``` fonction est_somme_precedents ( T : tableau[1..20] de entier, n : entier ) : logique début pour i de 3 à n faire si T[i] = T[i-1] + T[i-2] alors retourner Vrai finsi fin pour retourner Faux fin procedure afficher_indice ( T : tableau[1..20] de entier, n : entier ) début indice ← 0 pour i de 3 à n faire si T[i] = T[i-1] + T[i-2] alors indice ← i sortir de la boucle // on peut utiliser un retourner ou un break explicite finsi fin pour si indice = 0 alors affichage "Aucun indice trouvé" sinon affichage "Premier indice vérifiant la propriété : ", indice finsi fin algorithme MainSomme début lire n déclarer T[1..n] de entier pour i de 1 à n faire lire T[i] fin pour affichage "Tableau lu : " pour i de 1 à n faire affichage T[i], " " fin pour affichage "" // appel de la fonction ok ← est_somme_precedents(T, n) affichage "Propriété somme des deux précédents ? ", ok // appel de la procédure afficher_indice(T, n) fin ``` *Explication* : * La fonction parcourt le tableau à partir de l’indice 3 et retourne immédiatement `Vrai` dès qu’elle trouve une concordance ; sinon, après la boucle, elle retourne `Faux`. * La procédure cherche le **premier** indice qui satisfait la condition ; elle utilise une variable `indice` initialisée à 0 et, lorsqu’elle trouve une correspondance, elle enregistre l’indice et sort de la boucle (on peut imaginer un `sortir` ou un `retourner` anticipé). Après la boucle, elle teste si `indice` est resté à 0 pour décider du message à afficher. * Le tableau est passé par référence (afin de pouvoir le lire sans le copier) ; la taille `n` est passée par valeur. --- ### Exercice 5 (niveau difficile) **Énoncé** : Écrire une fonction `pgcd(a,b)` qui retourne le plus grand commun diviseur de deux entiers positifs `a` et `b` en utilisant l’algorithme d’Euclide (version itérative). Puis écrire une procédure `reduire_fraction(num, den)` qui, étant donné un numérateur et un dénominateur positifs, les réduit au plus simple en divisant les deux par leur PGCD. Enfin, écrire un algorithme qui lit deux entiers représentant une fraction, appelle la procédure et affiche la fraction réduite. **Corrigé** : ``` fonction pgcd ( a : entier, b : entier ) : entier début tandis que b ≠ 0 faire r ← a mod b a ← b b ← r fin pour retourner a fin procedure réduire_fraction ( num : entier, den : entier ) début div ← pgcd(num, den) num ← num div div den ← den div div fin algorithme TestReduction début lire num, den si num ≤ 0 ou den ≤ 0 alors affichage "Erreur : numérateur et dénominateur doivent être strictement positifs" sinon réduire_fraction(num, den) affichage "Fraction réduite : ", num, "/", den finsi fin ``` *Explication* : * La fonction `pgcd` implémente l’algorithme d’Euclide itératif : on remplace successivement `(a,b)` par `(b, a mod b)` jusqu’à ce que `b` devienne zéro ; alors `a` contient le PGCD. * La procédure reçoit le numérateur et le dénominateur, calcule leur PGCD, puis divise chacun par ce PGCD. Comme elle doit modifier les deux variables, on utilise le mode **valeur‑résultat** (ou référence, selon l’interprétation du cours). Dans la version ci‑dessus, on considère que les paramètres sont passés par valeur‑résultat : ils sont initialement copiés, modifiés, puis recopiés dans les variables de l’appelant. * L’algorithme principal lit la fraction, vérifie la positivité, appelle la procédure et affiche le résultat. --- ## Erreurs fréquentes | # | Erreur typique | Pourquoi elle se produit | Comment l’éviter | |---|----------------|--------------------------|------------------| | 1 | Oublier le `retourner` dans une fonction | On pense que la dernière expression évaluée est automatiquement retournée, comme dans certains langages de script. | Dans le pseudo‑code officiel, une fonction **doit** contenir une instruction explicite `retourner expression`. Vérifier chaque chemin d’exécution (y compris les branches `si…sinon`) pour s’assurer qu’un `retourner` est atteint. | | 2 | Confondre mode valeur et mode référence lorsqu’on veut modifier un argument | On croit que passer un tableau par valeur permet de le modifier, alors qu’en mode valeur seule la copie locale est modifiée. | Toujours se demander si l’on veut que la modification soit visible après l’appel. Si oui, choisir référence ou valeur‑résultat ; sinon, valeur suffit. | | 3 | Utiliser une procédure comme si elle retournait une valeur (ex. `x ← ma_procédure(a,b)`) | On applique mécaniquement la notation d’appel de fonction à une procédure. | Rappeler qu’une procédure ne possède pas de valeur de retour ; son appel est une instruction autonome. Si l’on a besoin d’un résultat, convertir la procédure en fonction ou utiliser un paramètre en mode résultat/valeur‑résultat. | | 4 | Oublier d’initialiser un paramètre en mode résultat avant de l’utiliser | En mode résultat, la valeur d’entrée de l’argument est considérée comme inutile, mais le paramètre doit recevoir une valeur avant d’être lu. | Dès l’entrée du sous‑algorithme, affecter une valeur par défaut (souvent 0 ou une valeur neutre) au paramètre de résultat, ou bien s’assurer que la première instruction lui assigne une valeur calculée à partir de l’argument (en le lisant avant toute modification). | | 5 | Dépasser la taille de la pile avec une récursion trop profonde | On écrit une fonction récursive sans penser à la profondeur d’appel (ex. factorielle de 1000). | Vérifier la profondeur maximale attendue ; si elle risque d’être élevée, préférer une version itérative ou utiliser une technique de récursion terminale si le langage le permet (dans le pseudo‑code scolaire, on reste généralement avec des valeurs petites). | | 6 | Ne pas réinitialiser une variable locale entre deux appels d’une même procédure | On croit que les variables locales sont automatiquement remises à zéro à chaque appel, alors qu’elles sont simplement nouvellement allouées mais peuvent contenir des valeurs indéterminées si on les réutilise sans les initialiser. | Toujours initialiser explicitement les variables locales au début du sous‑algorithme, surtout lorsqu’on les utilise dans des boucles ou des calculs. | | 7 | Confondre `et` et `ou` dans les conditions de recherche (ex. chercher un élément qui est soit égal à A soit égal à B) | On écrit `si T[i] = A et T[i] = B` alors que la bonne condition est `ou`. | Relire la logique de la condition : pour qu’une propriété soit vraie il suffit qu’une des possibilités se réalise → utiliser `ou`. Pour qu’elle soit vraie seulement si les deux sont vraies simultanément → utiliser `et`. | | 8 | Supposer qu’un tableau passé par référence est copié lorsqu’on le passe à une fonction qui ne le modifie pas | On pense que la référence implique toujours une copie coûteuse, ce qui peut conduire à des algorithmes inefficaces inutilement. | Se rappeler que le passage par référence ne copie pas le tableau ; il donne simplement un alias. Si la fonction ne modifie pas le tableau, il n’y a aucun coût supplémentaire lié à la référence. | En gardant ces points à l’esprit, l’élève pourra éviter les pièges les plus courants lorsqu’il conçoit, écrit et trace des algorithmes faisant appel à des fonctions et des procédures. --- *Fin du cours de référence.*