Institut Supérieur des Etudes
Technologiques de Mahdia
Support de cours
Algorithmique et
structures de
données 2
Enseignante : Mme Ikram Chebbi
Classe : TI2
2 01/03/2021
Fiche matière Objectifs généraux
Présentation Ce cours vise à:
Domaine de formation : Sciences et Approfondir les compétences
technologies acquises en algorithmique tout en
Mention : Technologies de l’informatique (TI) s’initiant aux notions et principes de
Parcours : Tronc Commun (TC) l’algorithmique avancée.
Semestre : S2 Se familiariser avec la notion de
pointeur et des structures de
Unité d’enseignement : Programmation et
données dynamiques (liste, piles, files
Structures Dynamiques
et arbres).
Volume horaire : 42 heures (28 cours – 14 TD)
Etre capable de transformer un
Coefficient : 2
schéma itératif simple en schéma
Prérequis: ASD 1
récursif.
Evaluation Moyens pédagogiques
• Evaluation orale: participation, interrogation.
• Présentation, tableau, support de
• Evaluation écrite : 2 tests (20mn chacun) , DS
cours , schémas, travaux dirigées.
(1 heure) et examen (1.5 heures). Ikram Chebbi-AP2
3 01/03/2021
Plan de cours
Chapitre 1: La récursivité
Chapitre 2: Les pointeurs
Chapitre 3: Les listes chaînées
Chapitre 4: Les piles
Chapitre 5: Les files
Chapitre 6: Les arbres
Ikram Chebbi-AP2
Chapitre 1
La récursivité
Ikram Chebbi-AP2
5 01/03/2021
Plan
Qu’est ce que la récursivité?
Fonctions récursives
Types de récursivité
Applications
Factorielle n
Suite de Fibonacci
Recherche dichotomique
Avantages et inconvénients
Ikram Chebbi-AP2
6 01/03/2021
Qu’est ce que la récursivité?
La récursivité est appuyée sur le raisonnement par récurrence.
Un objet est défini récursivement lorsqu'il y a référence à l'objet
lui même dans la définition.
On appelle récursive toute fonction ou procédure qui appelle
elle même.
Typiquement il s'agit d'une suite dont le terme général s'exprime
à partir de termes qui le précédent.
Par exemple la factorielle d'un nombre N donné est le produit des
nombres entiers inférieurs ou égaux à ce nombre N.
N!=N*(N-1)!=N*(N-1)*(N-2)!=….=N*(N-1)*…1
Ikram Chebbi-AP2
7 01/03/2021
Qu’est ce que la récursivité?
Exemple
Ecrire une fonction récursive Somme permettant de sommer les N
premiers entiers. La fonction peut être définie comme suit :
Somme (N) = N + Somme(N − 1)
Somme(0) = 0
FONCTION Somme (N : entier) : entier DEBUT
SI (N=0) ALORS
RETOURNER (0)
SINON
RETOURNER (N + Somme (N-1)) FIN SI
FIN
Ikram Chebbi-AP2
8 01/03/2021
Fonctions récursives
Fonction Procédure
Fonction FnRecursive(paramètres):Type Procédure ProRecursive(paramètres)
Var (facultatif) Var (facultatif)
Début Début
si TEST_D’ARRET //Pas obligatoire le test d’arrêt
Instructions du point d’arrêt si TEST_D’ARRET
retourner …. Instructions du point d’arrêt
sinon sinon
Instructions Instructions
// appel récursif // appel récursif
FnRecursive(paramètres changés) ProRecursive (paramètres changés)
Instructions Instructions
Fin si Fin si
Fin Fin
Ikram Chebbi-AP2
9 01/03/2021
Fonctions récursives
Un algorithme récursif va jouer sur les paramètres en entrée de la
fonction qui seront modifiés à chaque nouvel appel de la fonction
dans son propre corps.
Pour décrire l'algorithme sur une donnée d, on utilise l'algorithme lui
même sur un sous ensemble de d ou sur une donnée plus petite.
Comme dans le cas d’une boucle, il faut un cas d’arrêt où l’on ne
fait pas d’appel récursif.
Règles
• Ne jamais réappliquer l'algorithme sur des données plus
grandes.
• Toujours effectuer un test de terminaison.
Ikram Chebbi-AP2
10 01/03/2021
Fonctions récursives
Pour une fonction récursive, il y a trois aspects
fondamentaux :
le test d'arrêt : comment s'arrête la succession des appels ?
la décomposition des ou de la donnée(s) : sur quelle base
sont faits les appels successifs ?
l'empilement puis le dépilement en mémoire des appels
successifs: chaque appel possède en effet ses propres
variables locales en mémoire (comme s'il s'agissait des
appels des fonctions différentes).
Ikram Chebbi-AP2
11 01/03/2021
Fonctions récursives
Exemple:
Procédure Affiche( n:entier)
Début
si n≤0 alors
Ecrire("Valeur négative ")
Sinon
Affiche(n-1)
Ecrire(n)
FinSi
Fin
Algorithme: appel
Début
Affiche(5)
Fin
Qu’affiche ce programme?
Ikram Chebbi-AP2
12 01/03/2021
Fonctions récursives
Etape 1: empilement des appels
Affiche(5), Affiche(4), Affiche(3), Affiche(2), Affiche(1),
Affiche(0).
Affiche(0)
Etape 2: Arrêt des appels Affiche(1)
Affiche(2)
Affichage de n qui vaut 0.
Affiche(3)
Etape 3: dépilement des appels Affiche(4)
Affiche(5)
Affichage de n correspondant
Résultat: …………………….. Ikram Chebbi-AP2
13 01/03/2021
Fonctions récursives
Si on modifie la procédure affiche comme suit:
Procédure Affiche( n:entier)
Début
si n≤0 alors
Ecrire("Valeur négative ")
Sinon
Ecrire(n)
Affiche(n-1)
FinSi
Fin
Quel sera le résultat d’exécution?
Ikram Chebbi-AP2
14 01/03/2021
Fonctions récursives
Pile d’appels
Pour chaque appel de la fonction récursive, un espace
mémoire est alloué pour toutes ses données. Ceci est
libéré à la fin de l'exécution de la fonction.
Tous les appels des fonctions sont stockés dans une pile en
mémoire.
Un pile fonctionne comme une pile d'assiettes: les assiettes
à laver sont empilées les unes sur les autres au fur et à
mesure de leur arrivée. Au lavage, la dernière arrivée est
la première lavée ( Last In First Out).
Ikram Chebbi-AP2
15 01/03/2021
Fonctions récursives
Exécution
L’exécution se déroule en suivant une descente récursive ensuite une
remontée récursive, comme montre la figure suivante :
Ikram Chebbi-AP2
16 01/03/2021
Types de récursivité
Récursivité Simple Récursivité Croisée
Tous les appels récursifs apparaissent dans Pour ce type de récursivité, les appels récursifs
le corps du sous-programme récursif. sont provoqués par l’exécution d’autres
Une procédure récursive simple suit ce procédures ou fonctions suivant ce modèle :
modèle : SOUS_PROGRAMME P_rec (X)
DEBUT
PROCEDURE Prec (Paramètres) DEBUT Si (condition d’arrêt) ALORS
Si (condition d’arrêt) ALORS <Instructions>
SINON
<Instructions>
[<Instructions>]
SINON Q_rec (F(X))
[<Autres instructions>] [<Instructions>]
Prec (Paramètres changés) FIN SI FIN
[<Autres instructions>]
FIN SI FIN SOUS_PROGRAMME Q_rec (Y)
DEBUT
Si (condition d’arrêt) ALORS
<Instructions>
SINON
[<Instructions>]
P_rec (G(Y))
[<Instructions>]
FIN SI
FIN
Ikram Chebbi-AP2
17 01/03/2021
Application1: Factorielle n
Factorielle(n) = n*(n-1)*(n-2)*...*2*1
Cas géneral : Factorielle(n) = n*Factorielle(n-1)
Cas particuliers : Factorielle(1) = 1 et Factorielle(0) = 1
Ikram Chebbi-AP2
18 01/03/2021
Application 2: Suite de Fibonacci
Cas général: Fibo(n) = Fibo(n-1) + Fibo(n-2)
Cas particuliers: Fibo(0) = 1, Fibo(1) = 1
FONCTION FIB (N : entier) : entier
Debut
SI (N=0) ALORS
RETOURNER (1)
SINON
RETOURNER (FIB(N-2) + FIB (N-1))
FIN SI
FIN
Cette fonction nécessite 2 appels récursifs : fonction dyadique.
Ikram Chebbi-AP2
19 01/03/2021
Application 3:
On considère les deux suites mathématiques U et V définies
comme suit :
Un = 2×Vn-1 +3 si n >=1
Vn = 3×Un-1 +2 si n>=1
U0 = 1 ; V0 = 2
FONCTION U (n : entier) : entier DEBUT
SI (n=0) ALORS
RETOURNER (1) FONCTION V (n : entier) : entier DEBUT
SINON SI (n = 0) ALORS
RETOURNER (2*V(n-1) + 3) FIN SI RETOURNER (2)
FIN SINON
RETOURNER (3* U(n-1) + 2)
FIN SI
FIN
Ikram Chebbi-AP2
20 01/03/2021
Application 3: Recherche dichotomique
Recherche par dichotomie d'un élément x dans
un tableau trié T de dimension n.
Principe:
Comparer l‘élément x à une valeur située au milieu du
tableau.
Si cette valeur est différente de x, continuer la recherche
sur le demi-tableau susceptible de contenir x (partie
gauche ou partie droite du tableau).
Ikram Chebbi-AP2
21 01/03/2021
Recherche dichotomique
Ikram Chebbi-AP2
22 01/03/2021
Avantages et inconvénients
La programmation récursive est très proche de la définition
mathématique du problème.
Très facile à implémenter
→ Mais, ne pas oublier les critères d’arrêt car risque d’une boucle infinie.
Peut être coûteuse en temps machine.
Nécessite un espace mémoire important pour l’empilement des
appels.
Règle
• Toute fonction récursive peut être écrite sous forme
itérative (l'inverse n'est pas vrai).
Ikram Chebbi-AP2
