Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri

ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

Université Abdelhamid Mehri – Constantine 2

2021-2022. Semestre 1

Initiation à l’algorithmique

Chapitre 3 : Fonctions et Procédure

rocédures
(S
Sous Algorithmes)

Chargé de cours
Nom Grade Faculté/Institut Adresse e-mail
BADECHE Mohamed MCB Nouvelles Technologies algo.assistance
[email protected]

Etudiants concernés
Faculté/Institut Département Année Spécialité
Nouvelles Technologies MI Licence 1 Tronc commun

Objectifs :
Introduire la notion dee fonctions et procédures.
Apprendre à déclarer et appeler une fonction ou une procédure.
Faire la distinction entre les variables globales et locales.
Faire la distinction entre les paramètres formels et les variables effectives.
Connaître les types de passage de paramètres
paramè (par valeur et par référence).
Introduire la notion de récursivité.
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

Sommaire
Chapitre 3 : Fonctions et procédures ..................................................................................................................................... 1
3.1. Introduction à la notion de fonctions et procédures................................................................................................... 1
3.1.1. Exemples de sous algorithmes.............................................................................................................................. 2
3.2. Vocabulaire et notions de base ................................................................................................................................... 2
3.2.1. Nom et paramètres d’une fonction ou procédure ............................................................................................... 2
3.2.2. Notion d’appel d’une fonction ou procédure ....................................................................................................... 2
3.2.3. Différence entre fonction et procédure ............................................................................................................... 3
3.2.4. Déclaration d’une fonction ou procédure ............................................................................................................ 4
3.2.4.1. Déclaration de fonction et procédure en langages de programmation ........................................................ 5
3.2.5. Exemple d’un algorithme basé sur la notion de fonction..................................................................................... 6
3.2.6. Type de variables selon leur portée...................................................................................................................... 7
3.2.7. Types de paramètres et Types de passage de paramètres .................................................................................. 8
3.2.7.1. Passage par valeur et passage par référence ................................................................................................ 9
3.2.8. Remarques .......................................................................................................................................................... 11
3.2.8.1. Lecture et cas d’erreur ................................................................................................................................. 11
3.2.8.2. Optimalité des algorithmes ......................................................................................................................... 11
3.2.8.3. Convention syntaxique pour les types de passage ...................................................................................... 12
3.2.8.4. Cas d’omission du bloc ‘Variables’ d’un sous algorithme ............................................................................ 12
3.3. Récursivité ................................................................................................................................................................. 12
3.3.1 Récursivité croisée ............................................................................................................................................... 14
3.4. Exercices .................................................................................................................................................................... 15
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

Chapitre 3 : Fonctions et procédures

3.1. Introduction à la notion de fonctions et procédures

Supposons qu’on veut écrire un algorithme qui permet de calculer la formule suivante :

S = A! + B + 1 ! + C × 2 ! , tel que A, B et C fournis par l′utilisateur

Il sera donc question de calculer séparément trois factorielles, comme suit :

Algo Formule
Variables
A, B, C, i, F1, F2, F3, S : Entier
Début
Rpt
Lire(A, B, C)
Jsq A ≥ 0 Et B ≥ -1 Et C ≥ 0

/* calcul de A! */
F1 1
Pour i 2àA:
F1 F1 * i
FPour
/* calcul de (B+1)!*/
F2 1 Calcul de la factorielle
Pour i 2 à B+1 :
trois fois
F2 F2 * i
FPour
/* calcul de (C×2)!*/
F3 1
Pour i 2 à C :
F3 F3 * i
FPour

S F1 + F2 + F3
Ecrire(S)
Fin
.

Remarquez ici, qu’on était obligé de répéter le même traitement de calcul de la factorielle trois fois.
Pour éviter la répétition et réduire la complexité, l’algorithmique offre la possibilité de diviser l’algorithme
principal en sous algorithmes. Dans notre exemple, grâce à cette nouvelle notion, on pourra définir le bloc de
calcul de la factorielle une fois pour toute, et l’utiliser trois (3) fois dans l’algorithme principal. C’est ce que
nous allons faire dans la suite de ce chapitre qui va détailler la notion de sous algorithmes.

1
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

3.1.1. Exemples de sous algorithmes

Les sous algorithmes peuvent être divisés en deux catégories : les fonctions et les procédures.
Depuis le début de notre cours, nous avons utilisé deux procédures et une fonction, même si on ne les avait pas
qualifiées comme telles. Lire et Ecrire sont deux procédures prédéfinies, alors que Racine que nous avons
utilisée dans le problème de résolution d’une équation du deuxième degré, est une fonction.
On remarque que toutes les trois ont un point commun ; c’est le fait qu’elles sont toujours suivies de
parenthèses : Lire(N), Ecrire(S) et Racine(Delta). En voici, une première règle d’écriture des sous algorithmes,
qui doivent toujours être suivis de parenthèses.

3.2. Vocabulaire et notions de base

3.2.1. Nom et paramètres d’une fonction ou procédure
Chaque fonction ou procédure a un nom arbitraire suivi de parenthèses qui peuvent contenir un ou plusieurs
paramètres (Voire aucun dans certains cas particuliers) :
Nom de la procédure Nom de la procédure
Lire(a,b,c) Paramètres de la procédure
Lire(a,b,c) Ecrire(S)
Ecrire(S) Paramètre de la procédure

Nom de la fonction
X1
X1 (-b
(-b ++ Racine(Delta))
Racine(Delta)) Paramètre de la fonction
3.2.2. Notion d’appel d’une fonction ou procédure
Il y a deux endroits où on peut rencontrer une fonction ou une procédure. Le premier est dans le bloc Variables
de l’algorithme principal1 pour la déclaration (la définition), et le deuxième dans le corps de l’algorithme
principal1 pour l’appel (l’utilisation) de la fonction ou de la procédure.
Dans l’exemple suivant, il y a appels des procédures Lire et Ecrire et de la fonction Racine :
Algo Principal
Variables
/* Il n’y a pas de Déclaration ici des procédures Lire, Ecrire, et de la fonction Racine, puisque considérées
comme prédéfinies */
a, b, c, Delta, X1, X2 : Réel
Début
/* Exemples d’appel de sous algorithmes */
Rpt
Lire(a, b, c) Appel de la procédure Lire avec 3 paramètres
Jsq a ≠ 0
Delta b*b – 4*a*c
Si Delta < 0 :
Ecrire("pas de solution dans R")
Appel de la procédure Ecrire avec un paramètre de type chaîne de caractères
Sinon
X1 (-b + Racine(Delta) ) / (2*a)
X2 (-b - Racine(Delta) ) / (2*a) Appel de la fonction Racine avec un seul paramètre de type réel
Ecrire(X1, X2)
Appel de la procédure Ecrire avec deux paramètres de type réel
Fin
Fin
On appelle une fonction ou une procédure par son nom suivi de ses paramètres (arguments) entre parenthèses.

1
Ou l’algorithme appelant de façon générale.
2
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

Dans cet exemple dee problème de résolution d’une équation du deuxième degré, nous avons écrit dans
l’algorithme principal: X1 (-b + Racine(Delta) ) / (2*a)
C’était là, un appel (une utilisation) de la fonction Racine que nous avons considérée comme prédéfinie et de
ce fait, nous ne l’avons pas déclarée nous même dans la partie Variables de l’algorithme.

De même pour Lire et Ecrire, qui sont des procédures prédéfinies

prédéfinie qu’on appelle (qu’on utilise) dans les corps
des algorithmes.

La fonction Racine a toujours un seul paramètre, tandis que Lire et Ecrire peuvent
vent avoir plusieurs paramètres.

3.2.3. Différence entre fonction et procédure

Remarquez qu’on a pu faire appel à la fonction Racine dans une expression arithmétique qui a été affectée
affecté à
une variable : X1 (-b + Racine(Delta
Delta))
Mais on n’a jamais écrit une forme comme : Y Lire(N) ou Z Ecrire(S)
Ce qui constitue la différence entre une fonction et une procédure : laa fonction retourne un résultat dans son
nom, ce qui permet de l’appeler dans une expression de calcul et d’affectation, alors que la procédure ne
retourne pas de résultat dans son nom, ce qui fait qu’on ne trouve jamais un appel de procédure tel que :
Y Nom_Procédure(...) , ou un appel de fonction comme : Nom_fonction(...) , sans affectation ou affichage.

Voici des exemples valides et non valides d’appels de fonctions et de procédures :

Appels valides Appels non valides

(param1, param2, ...)

Nom_procédure(param1, (param1, param2, ...)
Nom_fonction(param1,

R (param1, param2,...)
Nom_fonction(param1, R (param1, param2,...)
Nom_procédure(param1,

R (param1, param2,...) + Y / Z
Nom_fonction(param1, R (param1, param2,...) + Y
Nom_ procédure(param1,

Ecrire(Nom_fonction(param1,
(param1, param2,...)) Ecrire(Nom_ procédure(param1,
procédure param2,...))

Donc, la fonction diffère principalement de la procédure,

procédure par le fait qu’un résultat est retourné dans le nom de la
fonction, à la différence d’une procédure qui n’a pas de résultat dans son nom2. Cette particularité des fonctions
représente leur avantage, qui permet d’en faire appel directement dans des expressions de calcul ou d’affichage.

Le résultat est retourné dans le

nom de la fonction X1 (-b + Racine(Delta))

Il n’y a pas de résultat dans le

nom d’une
’une procédure
Lire(a,b,c)

2
Ceci ne veut pas dire que la procédure ne doit pas retourner de résultat, ou que la fonction doit retourner un seul résultat.
Il y a possibilité de retourner des résultats non pas dans le nom de la fonction, mais
mais dans des paramètres de sortie, comme
nous allons voir dans la section 3.2.7.
3
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

3.2.4. Déclaration d’une fonction ou procédure

La syntaxe de déclaration d’un sous algorithme (fonction ou procédure) est très similaire à la déclaration d’un
algorithme. Un sous algorithme a un Entête, un bloc Variables, et un Corps (entre les deux mots clés Début et
Fin).

La différence entre la déclaration d’une fonction et d’une procédure est :

- Le mot clé fonction ou procédure au niveau de l’entête.
- La fonction a un type au niveau de l’entête (puisque elle retourne un résultat dans son nom), tandis que
la procédure n’en a pas.
- La dernière instruction du corps d’une fonction, est l’affectation du résultat au nom de la fonction.

Déclaration d’une fonction Déclaration d’une procédure

Fonction Nom_fonction (Param1 : Type , ...) : Type Procédure Nom_procédure (Param1 : Type , ...)
Variables Variables
... ...
Forme
Début Début
générale ... ...
Fact …
Fin Fin
Fonction Fact (N : Entier) : Entier Procédure Fctrl (N : Entier, Ref R : Entier)
Variables Variables
F, i : Entier F, i : Entier
Exemple Début Début
F 1 F 1
de la
Pour i 2 à N : Pour i 2 à N :
factorielle F F*i F F*i
FPour FPour
Fact F R F
Fin Fin

Examinons de près l’exemple de déclaration de la fonction Fact (abréviation de Factorielle) :

Fonction Fact (N : Entier) : Entier Il s’agit d’une fonction du nom : Fact, qui a comme
Variables
paramètre une valeur entière, et qui retourne un résultat de
F, i : Entier
Début type entier dans son nom.
F 1
Pour i 2 à N :
F F*i Calcul de la factorielle d’un nombre N.
FPour

Fact F Affectation du résultat au nom de la fonction.

Fin

4
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

3.2.4.1. Déclaration de fonction et procédure en langages de programmation

Voici la traduction de l’exemple de déclaration de la fonction Fact en Visual Basic et en langage C :

Algorithmique Visual Basic Langage C

Fonction Fact (N : Entier) : Entier Function Fact(N As Integer) As Integer int Fact(int N)
Variables {
F, i : Entier Dim F, i As Integer int F, i;
Début
F 1 F=1 F = 1;
Pour i 2àN: For i = 2 To N for(i=2;i<=N;i++)
F F*i F=F*i F = F * i;
FPour Next
Fact F Fact = F return(F);
Fin End Function }

De même pour la déclaration de la procédure Fctrl en Visual Basic et en langage C++ :

Algorithmique Visual Basic Langage C++

Procédure Fctrl(N : Entier, Ref R : Entier) Sub Fctrl(N As Integer, ByRef R As Integer) void Fctrl(int N, int &R)
Variables {
F, i : Entier Dim F, i As Integer int F, i;
Début
F 1 F=1 F = 1;
Pour i 2àN: For i = 2 To N for(i=2;i<=N;i++)
F F*i F=F*i F = F * i;
FPour Next
R F R=F R=F;
Fin End Sub }

Nous allons voir la signification du mot clé Ref, ainsi que le fonctionnement de cette procédure dans la section
3.2.7.

5
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

3.2.5. Exemple d’un algorithme basé sur la notion de fonction

Maintenant qu’on connait la syntaxe de déclaration et d’appel d’une fonction, nous allons transformer
l’algorithme introductif de ce chapitre, avec utilisation de la notion de fonction, qui va le rendre plus concis,
plus simple à écrire et à assimiler, et va nous éviter la redondance (la répétition),

Algorithme de l’exemple introductif Algorithme équivalent avec utilisation d’une fonction

Algo Formule Algo Principal
Variables Variables
A, B, C, i, F1, F2, F3, S : Entier A, B, C, S : Entier
Début
Fonction Fact (N : Entier) : Entier
Variables
F, i : Entier
Début
F 1
Pour i 2 à N :
F F*i
FPour
Fact F
Fin

Rpt
Lire(A, B, C)
Jsq A ≥ 0 Et B ≥ -1 Et C ≥ 0

/* calcul de A! */
F1 1
Pour i 2 à A : Début
F1 F1 * i Rpt
FPour Lire(A,B,C)
Jsq A ≥ 0 Et B ≥ -1 Et C ≥ 0
/* calcul de (B+1)!*/
F2 1 S Fact(A) + Fact(B+1) + Fact(C*2)
Pour i 2 à B+1 : Ecrire(S)
F2 F2 * i Fin
FPour
/* calcul de (C×2)!*/
F3 1
Pour i 2 à C*2 :
F3 F3 * i
FPour

S F1 + F2 + F3
Ecrire(S)
Fin

6
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

3.2.6. Type de variables selon leur portée

Avec l’utilisation de la notion de fonctions et procédures, la déclaration de variables peut se faire dans trois (3)
endroits :

1. Dans le bloc Variables de l’algorithme principal,

2. Entre les parenthèses dans l’entête de déclaration du sous algorithme,
3. Dans le bloc Variables du sous algorithme.

Le premier type est appelé Variable Globale, le deuxième est appelé Paramètre et le troisième est qualifié de
Variable Locale.

Algo Principal Variable Globale

Variables Paramètre
A, B, C, S : Entier
Fonction Fact (N : Entier) : Entier
Variables Variable Locale
i, F : Entier
Début
F 1
Pour i 2 à N :
F F*i
FPour
Fact F
Fin
Début
Rpt
Lire(A, B, C)
Jsq A ≥ 0 Et B ≥ -1 Et C ≥ 0
S Fact(A) + Fact(B+1) + Fact(C*2)
Ecrire(S)
Fin

Dans l’exemple précédent, la variable S est déclarée dans le bloc Variables de l’algorithme principal, et
considérée de ce fait comme étant variable globale, la variable N est déclarée dans l’entête de la fonction, et
considérée par conséquent comme paramètre, et la variable F est déclarée dans le bloc Variables de la
fonction, et est considérée comme variable locale.

La principale différence entre les trois types, est la portée : la variable locale F n’est utilisable qu’à l’intérieur
de la fonction. Il n’est pas possible par exemple, d’écrire dans l’algorithme principal une instruction comme :
F F+1, puisque F n’est connue qu’à l’intérieur de la fonction. L’inverse n’est pas vrai, dans la fonction on
peut utiliser la variable globale S en cas de besoin, puisque S est une variable globale qui est connue à la fois,
dans l’algorithme principal et dans la fonction.

La protée du paramètre N est comme la portée des variables locales : N n’est connue qu’à l’intérieur de la
fonction. Remarquez par contre, que dans l’appel de la fonction, on n’a pas utilisé la variable N, mais plutôt A,
B+1 et C*2. C’est exactement ce qui fait la force de la notion de paramètre. Les variables paramètres de la
déclaration d’une fonction ou procédure, peuvent être remplacées lors de l’appel, par une valeur, par une
variable, ou par une expression calculable.

7
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

Donc on définit la fonction Fact en utilisant le paramètre N, mais on peut en faire appel librement, par :
- Fact(6)
- Fact(A)
- Fact(B+1)
- ...

Dans ce niveau de première année, il est fortement conseillé de différencier les noms de variables paramètres
lors de la déclaration (variables formels), des noms de variables correspondantes utilisées lors de l’appel dans
l’algorithme principal (variables effectives).

Dans le cas où la fonction ou la procédure comporte plusieurs paramètres, c’est l’ordre qui permet d’enlever
l’ambigüité.

3.2.7. Types de paramètres et Types de passage de paramètres

Il y a deux types de paramètres, les paramètres d’entrée et les paramètres de sortie par rapport à la fonction ou
la procédure. Le premier type constitue les valeurs d’entrée qu’utilisent la fonction ou la procédure, et le
deuxième type représente les résultats de sortie.
Exemples :

Entête Description Exemple d’appel

La fonction Fact à un paramètre
d’entrée de type entier, et n’a pas de
Fonction Fact (N : Entier) : Entier paramètre de sortie, puisque le résultat Ecrire(Fact(6))
de type entier sera retourné dans le
nom de la fonction.
La procédure Fctrl à un paramètre
d’entrée de type entier, et un deuxième
Fctrl(6,Res)
Procédure Fctrl(N : Entier, Ref R : Entier) paramètre de sortie qui contiendra le
Ecrire(Res)
résultat du calcul de la factorielle du
premier paramètre.
La fonction Puiss à deux paramètres
d’entrée de type entier, et n’a pas de
paramètre de sortie, puisque le résultat Ecrire(Puiss(2,5))
Fonction Puiss(B, P : Entier) : Réel
de l’élévation à la puissance, qui est /* 32 = 25 */
du type réel, sera retourné dans le nom
de la fonction.
La procédure Psnc à deux paramètres
d’entrée de type entier, et un troisième
Psnc(2,5,W)
Procédure Psnc(B, P : Entier, Ref R : Réel) paramètre de sortie qui contiendra le
Ecrire(W)
résultat de l’élévation à la puissance
du premier paramètre par le deuxième.
La fonction PGCD calcule le PGCD
Fonction PGCD(A, B : Entier) : Entier de deux entiers passés en paramètre et Ecrire(PGCD(12,15))
retourne le résultat dans son nom.
La fonction PGCD2 calcule le PGCD
Procédure PGCD2(A, B : Entier, Ref R : de deux entiers passés en paramètre et PGCD(12,15,P)
Entier) met le résultat dans un troisième Ecrire(P)
paramètre de sortie.
8
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

La fonction Division à deux

paramètres d’entrée de type entier, et
Fonction Division(A, B : Entier, Ref R : retourne leur quotient de la division Ecrire(Division(23,5,Rst))
Entier) : Entier dans le nom de la fonction, et le reste Ecrire(Rst)
de la division, dans un troisième
paramètre de sortie.
La procédure Division2 à deux
paramètres d’entrée de type entier, et
Procédure Division2(A, B : Entier, Ref Q, R Division2(23, 5 ,Qt ,Rst)
met leur quotient et leur reste de
: Entier) Ecrire(Qt, Rst)
division, dans le troisième et le
quatrième paramètre respectivement.
La procédure Permutation à deux
paramètres réels d’entrée et de sortie X 3
Y 5
Procédure Permutation(Ref A, B : Réel) en même temps, puisqu’elle prend les
Permutation(X, Y)
valeurs des deux paramètres et les Ecrire(X, " ", Y) /* 5 3 */
permute entre elles.

A partir des exemples précédents, on constate ce qui suit :

- L’étape d’élaboration de l’entête d’une fonction ou procédure constitue une étape très importante dans
l’écriture des sous algorithmes.
- Toute fonction peut être transformée en procédure.
- Les paramètres de sortie sont toujours précédés par le mot clé Ref.

3.2.7.1. Passage par valeur et passage par référence

Il y a deux types de passage de paramètre : passage par valeur (Val) et passage par référence (Ref)3. Le premier
correspond aux paramètres d’entrée et le deuxième aux paramètres de sortie.

Quand on passe (on donne) un paramètre en valeur lors de l’appel, la valeur de la variable paramètre est gardée
telle quelle après appel, même si le sous algorithme l’avait modifié. Ce type de passage est utilisé pour protéger
les paramètres d’entrée, comme le cas de la variable M de l’exemple suivant.

Le passage par référence, par contre, fait l’inverse et permet de modifier la valeur du paramètre de sortie après
appel dans l’algorithme principal. C’est le cas de la variable Res de l’exemple suivant.

3
Dans ce niveau de première année, les termes suivants sont équivalents : passage par référence, par variable, et par
adresse. On a choisit d’utiliser Ref (référence) puisque ça correspond au vocabulaire le plus utilisé aujourd’hui avec des
langages comme Java, Python, VB ...
9
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

1er exemple 2ème exemple

Algo Principal1 Algo Principal2
Variables Variables
M, Res : Entier M, Res : Entier
Procédure Fctrl1 (Val N : Entier, Ref F : Entier) Procédure Fctrl2 (Ref N : Entier ; Val F : Entier)
Variables Variables

Début Début
F 1 F 1
TQ N > 1 : TQ N > 1 :
F F*N F F*N
N N-1 N N-1
FTQ FTQ
Fin Fin
Début Début
Rpt Rpt
Lire(M) Lire(M)
Jsq M ≥ 0 Jsq M ≥ 0
Res 0 Res 0
Fctrl1 (M, Res) Fctrl2 (M, Res)
Ecrire(M, Res) Ecrire(M, Res)
Fin Fin
Exécution
M Res Ecran M Res Ecran
Rpt Rpt
Lire(M) 5 Lire(M) 5
Jsq M ≥ 0 Jsq M ≥ 0
Res 0 0 Res 0 0
Fctrl1(M, Res) 5 120 Fctrl2(M, Res) 1 0
Ecrire(M, Res) 5 120 Ecrire(M, Res) 1 0
Dans cet exemple, le pseudo code de calcul de la factorielle avait affecté la variable d’entrée M et l’avait
modifié. Il était intéressant de garder sa valeur initiale avant appel, pour pouvoir l’utiliser après dans d’autres
traitements éventuels. C’est pour cette raison qu’il était plus convenable de passer le premier paramètre en
valeur.

Par contre, pour avoir le bon résultat de calcul de la factorielle, il a fallut passer le deuxième paramètre par
référence. Autrement, sa valeur initiale aurait été inchangée comme ce qui s’est passé dans le deuxième
exemple (Res a gardé sa valeur égale à 0).

Dans ce cas, le premier exemple correspond aux bons passages de paramètres :

Procédure Fctrl1 (Val N : Entier, Ref F : Entier)

Remarquez qu’on a pu dans certains exemples de ce chapitre, ne pas mettre carrément, le type de passage. Ceci
est dû au fait, que si on omet de mettre le type de passage, il est considéré par défaut, comme par valeur.4
On aurait pu donc écrire : Procédure Fctrl1 (N : Entier, Ref F : Entier)

Un autre exemple d’illustration de la notion de passage par référence, qui est considéré d’ailleurs comme
exemple type, est la procédure permutation :

4
Le passage par défaut dans les langages de programmation diffère selon le langage. En langage C, c’est le passage par
valeur qui est par défaut, mais en VB, c’est l’inverse, c’est le passage par référence.
10
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

1er exemple 2ème exemple

Algo Permute1 Algo Permute2
Variables Variables
X, Y : Réel X, Y : Réel
Procédure Permutation1(Ref A, B : Réel) Procédure Permutation2(Val A, B : Réel)
Variables Variables
C : Réel C : Réel
Début Début
C A C A
A B A B
B C B C
Fin Fin
Début Début
Lire(X, Y) Lire(X, Y)
Permutation1(X, Y) Permutation2(X, Y)
Ecrire(X, Y) Ecrire(X, Y)
Fin Fin
Exécution
X Y Ecran M Res Ecran
Lire(X, Y) 3 5 Lire(X, Y) 3 5
Permutation1(X, Y) 5 3 Permutation2(X, Y) 3 5
Ecrire(X, Y) 5 3 Ecrire(X, Y) 3 5

Ici, il est impératif de passer les paramètres par référence, sinon le mécanisme de protection des paramètres
passés par valeur, empêchera la permutation effective des deux variables.

3.2.8. Remarques
3.2.8.1. Lecture et cas d’erreur
Les sous algorithmes ne valent que s’ils sont paramétrables, c’est pour cela que dans la plupart des cas, on leur
passe les valeurs d’entrées en paramètres. Ce qui fait que la lecture à partir des données de l’utilisateur est
effectuée dans l’algorithme principal la plupart du temps, et non pas dans les sous algorithmes.

De même pour les cas d’erreur, qui sont relatifs aux données saisies par l’utilisateur, ils sont la plupart du
temps, traités dans l’algorithme principal et non pas dans les sous algorithmes.

Rappeler vous à ce fait, le cas de la fonction Racine : on vérifie si le paramètre Delta est positif dans
l’algorithme principal et non pas à l’intérieur de la fonction elle-même (supposée d’ailleurs comme prédéfinie).

3.2.8.2. Optimalité des algorithmes

L’utilisation des sous algorithmes apporte plus d’aisance à l’écriture des algorithmes, évite la redondance, et
réduit la complexité, mais ceci ne veut pas dire nécessairement, des algorithmes optimaux du point de vue
temps d’exécution et espace mémoire. Les appels de sous algorithmes peuvent consommer plus de temps et
d’espace mémoire.

11
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

3.2.8.3. Convention syntaxique pour les types de passage

Dans l’entête de déclaration des sous algorithmes, On sépare les paramètres qui ont des types de passage
différents, soit par virgule ou par point virgule (;) comme :

Procédure Puiss(B : Entier, P : Entier , Ref R : Entier) ou Procédure Puiss(B : Entier, P : Entier ; Ref R : Entier)

Il est possible de procéder à des déclarations condensées des paramètres du même type de donnée et du même
type de passage, comme :

Procédure Puiss(B, P : Entier, Ref R : Entier), mais pas : Procédure Puiss(B, P, Ref R : Entier)

3.2.8.4. Cas d’omission du bloc ‘Variables’ d’un sous algorithme

Il arrive que le bloc Variables d’une fonction ou procédure ne contienne aucune déclaration. Dans ce cas, on
pourra tout simplement l’omettre comme dans l’exemple suivant :

Fonction PlusGrand(A, B: Entier) : Entier

Début
Si A > B :
PlusGrand A
Sinon
PlusGrand B
FSi
Fin

3.3. Récursivité
Nous avons vu précédemment dans ce chapitre, comment déclarer un sous algorithme, et comment l’appeler à
partir de l’algorithme principal. Mais, il n’y a pas que l’algorithme principal qui peut faire appel aux fonctions
et procédures ; un sous algorithme peut faire appel à un autre. Mieux encore, un sous algorithme peut faire
appel à lui-même. On appelle cette notion ‘la récursivité’.

Soit l’exemple suivant :

Une suite U de nombres entiers est définie par : U1 = 0 et Un+1 = 2×Un + 3, pour n ≥ 1

On veut écrire un algorithme qui permet de calculer un terme donné de la suite U.

Ici pour calculer un terme de la suite, il faut calculer tous les termes précédents : pour calculer U5, il faut
calculer U4, et pour calculer U4, il faut auparavant, calculer U3, et pour calculer U3, il faut calculer U2, et pour
calculer U2, il faut avoir U1, le quel vaut 0.

12
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

Les deux algorithmes suivants proposent une solution pour le calcul d’un terme donné de la suite U. Le premier
algorithme présente une solution itérative (opposée de récursive), mais le deuxième algorithme présente une
solution récursive qui est beaucoup plus simple à écrire :

Solution Itérative Solution Récursive

Algo Sol_Itérative Algo Sol_Récursive
Variables Variables
n : Entier n : Entier
Fonction U(ind : Entier) : Entier Fonction U(ind : Entier) : Entier
Variables Début
i, Act, Pre : Entier Si ind = 1 :
Début U 0
Si ind = 1 : Sinon
U 0 U 2*U(ind-1) + 3
Sinon FSi
Pre 0 Fin
PR i 2 à ind :
Act 2*Pre + 3
Pre Act
FPr
U Act
FSi
Fin
Début Début
Rpt Rpt
Lire(n) Lire(n)
Jsq n ≥ 1 Jsq n ≥ 1
Ecrire(U(n)) Ecrire(U(n))
Fin Fin

L’exécution des appels imbriqués de la fonction récursive est illustrée sur cette vidéo :
https://youtu.be/VXnc99JshF8

Pour pouvoir écrire une solution récursive, il convient de trouver une relation qui permet d’exprimer le
problème en fonction de lui-même, mais avec des données (paramètres) moins complexes (plus simples),
jusqu’à arriver à un point terminal (un point d’arrêt)5 où la solution est connue et triviale.

Notons que cette relation récursive n’est pas toujours possible à trouver pour tout type de problème.

5
On pourra l’appeler aussi ‘point de départ’ si on veut. Ce point correspond à ce qu’appellent certaines références ‘cas
trivial’.
13
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

Voici quelques exemples de relations récursives :

Relation récursive Point(s) d’arrêt

Factorielle d’un nombre entier
!= −1 !× 0! = 1
positif
PGDC (plus grand diviseur PGCD A − B, B si A > %
commun) de deux nombres PGCD A, B = PGCD A, B = A si A = B
PGCD A, B − A si B > &
entiers strictement positifs
Conversion binaire d’un nombre
N ( = N Div 2 ( × 10 + *+, 2 0 ( = 0
entier positif
Reste de division de deux
nombres entiers strictement & *+, % = & − % *+, % -. & ≥ % & *+, % = % -. & < %
positifs

Une fois la relation récursive trouvée, la solution algorithmique devient très simple à écrire, quoi qu’elle est
coûteuse en terme de temps d’exécution et d’espace mémoire.

3.3.1 Récursivité croisée

Quand deux (ou plusieurs) sous algorithmes s’appellent mutuellement entre eux, on appelle ce type de
récursivité : ‘Récursivité croisée’.

Exemple : soit les deux suites U et V définies comme suit :

U1 = 1, Un+1 = Vn + 4
V1 = 2, Vn+1 = 3 × Un

L’ordre de déclaration des sous algorithmes entre eux, n’est pas important6. On aura donc la déclaration :

Fonction U(n : Entier) : Entier

Début
Si n = 1 :
U 1
Sinon
U V(n-1) + 4
FSi
Fin

Fonction V(n : Entier) : Entier

Début
Si n = 1 :
V 2
Sinon
V 3* U(n-1)
FSi
Fin

6
C’est le cas de beaucoup de langages de programmation. En langage C par contre, il suffit de rajouter l’entête de la
deuxième fonction avant la première.

14
Cours : Initiation à l’algorithmique Université Constantine 2 – Abdelhamid Mehri
ère
Dr. Mohamed BADECHE Tronc Commun – MI, Faculté NTIC – 1 Année (2021-2022)

3.4. Exercices
Exercice 01:
a- Écrire une fonction qui retourne la factorielle d’un nombre entier passé en paramètre.
b- Utiliser la fonction précédente dans un algorithme principal qui demande un nombre entier et affiche sa
factorielle.
c- Utiliser la fonction de la question a dans un algorithme principal pour afficher le résultat de la formule :
1 1 1 1
Formule1 = 1 + + + + ⋯
1! 2! 3! 9!
d- Utiliser la fonction de la question a dans un algorithme principal pour afficher le résultat de la formule :
9 8 7 1
Formule2 = 1 + + + + ⋯
1! 2! 3! 9!
Exercice 02:
a- Écrire une fonction qui vérifie si un nombre est premier ou non, et utiliser la dans un algorithme principal
pour calculer la somme des Nb premiers nombres premiers.
b- Récrire le même algorithme en utilisant, une procédure pour vérifier si un nombre est premier ou non.
Exercice 03:
a- Écrire une fonction qui retourne le PPCM de deux entiers strictement positifs, et utiliser la dans un
algorithme principal pour calculer le PPCM de 20 nombres fournis par l’utilisateur.
b- Récrire le même algorithme en utilisant cette fois, une procédure pour le calcul du PPCM.
Exercice 04:
a- Écrire une fonction récursive qui retourne la factorielle d’un nombre naturel.
b- Écrire une fonction récursive qui retourne l’élévation d’un nombre B non nul à la puissance P (BP), tel que P
strictement positif.
c- Écrire une fonction récursive qui retourne le PGCD de deux nombres entiers strictement positifs.
d- Écrire une fonction itérative et une autre récursive, qui ont comme paramètre un nombre entier strictement
positif et rend sa conversion en binaire.
Exercice 05 :
a- Écrire un sous algorithme récursif qui a comme paramètre un entier n positif, et rend le terme de la suite de
Fibonnacci correspondant (U0 = 0, U1 = 1, Un = Un-1 + Un-2 pour tout n > 1).
b- Soit les deux suites suivantes définies par récurrence croisée :
U1 = 0, Un+1 = 2×Un + Vn
V1 = 4, Vn+1 = Vn + Un /5
Écrire leurs fonctions récursives correspondantes.

15