Algorithmique & structures de données 1er Niveau
LECON N° 8
LA RECURSIVITE
ISET CHARGUIA 1
Algorithmique & structures de données 1er Niveau
Sommaire
1. RAPPEL SUR LES PROCEDURES ..................................................................................................... 90
1.1 DEFINITION....................................................................................................................................... 90
1.2 ADRESSE DE RETOUR ........................................................................................................................ 90
1.3 PILE .................................................................................................................................................. 90
1.4 LES PARAMETRES .............................................................................................................................. 91
2. LA RECURSIVITE ................................................................................................................................ 92
2.1 DEFINITION....................................................................................................................................... 92
2.2 TYPES DE RECURSIVITE ..................................................................................................................... 93
2.3 CONDITION D’ARRET ........................................................................................................................ 93
2.4 SCHEMA DE FONCTIONNEMENT D’UNE PROCEDURE OU FONCTION RECURSIVE .............................. 94
2.5 COMPARAISON ENTRE LES SCHEMAS ITERATIF ET RECURSIF............................................................. 94
ISET CHARGUIA 2
Algorithmique & structures de données 1er Niveau
1. Rappel sur les procédures
Définition
Une procédure, identifié par son nom, est une suite d’actions. Elle permet de :
Faciliter la modularité de l’algorithme
Isoler des parties de l’algorithme qui son utilisées à plusieurs
reprises ce qui ne nécessite pas la réécriture des même lignes de
codes plusieurs fois.
Le programmeur économise donc du temps de saisie mais aussi de l’espace
mémoire puisque le code correspondant n’est stocké qu’une seule fois.
Une procédure P doit être écrite une seule fois dans un algorithme A et peut être
appelée plusieurs fois par A.
Adresse de retour
Les instructions d’un programme d’exécutent les unes à la suite des autres.
Cependant, certaines instructions peuvent contrarier cet enchaînement séquentiel (les
instructions conditionnelles, les instructions itératives, les procédures et les
fonctions).
Un emplacement mémoire spécifique ou registre appelé COMPTEUR ORDINAL
contient l’adresse de la prochaine instruction à exécuter.
Lors du retour de la procédure, le CO reçoit l’adresse de l’instruction placée après
son appel. Cette instruction se situe dans le programme appelant.
Pile
Pour que le retour de l’appel soit correctement géré, avant l’appel de la procédure, le
processeur empile l’adresse de retour au programme appelant.
Après son exécution, le processeur peut retrouver cette adresse de retour en la
dépilant.
ALGORITHME xxx Déroulement de l’exécution Etat de la Pile
Procédure P
Début
I1
I2
In
Fin P
Début
A1 A1
P Appel de P Empilement adr
A2 Exécution I1
I2
In
An
Fin xxx retour Dépilement adr
A2
ISET CHARGUIA 3
Algorithmique & structures de données 1er Niveau
Les paramètres
Les paramètres constituent un mécanisme de substitution permettant
l’utilisation répétée d’une même procédure avec un jeu de données différent.
Les paramètres placés dans l’appel de procédure s’appellent des paramètres
effectifs. Ceux placés dans la déclaration de la procédure s’appellent des
paramètres formels.
Passage de paramètres
Paramètres passés par Valeur
La transmission par valeur d’un paramètre consiste à recopier la valeur à transférer
dans la procédure elle-même. Cette dernière travaille alors avec cette copie sans
toucher en quelque sorte à la valeur d’origine.
La transmission par valeur est une transmission à sens unique. En effet, il y a
transfert d’informations lors de l’appel de la procédure, il n y a en revanche aucun
échange lors du retour de la procédure.
La transmission par valeur permet de fournir de l’information à la procédure
mais en aucun cas de recueillir un quelconque résultat.
Ainsi, tous les paramètres qui constituent les données d’entrée pour les
calculs internes à la procédure seront déclarés en paramètres par valeur.
Variable Copie de la
d’origine variable
(allocation nlle
zone mémoire)
Paramètres transmis par variable
Lors d’un appel d’une procédure, il n y aura non plus recopie d’une valeur mais
transmission de son adresse donc de son emplacement dans l’algorithme appelant.
Dans ces conditions, la procédure ne travaillera plus sur une copie mais sur la
valeur d’origine elle-même. Elle peut donc éventuellement la modifier.
Ainsi, tous les paramètres qui contiennent un résultat de la procédure doivent
être déclarés en paramètres par variables séparés des ; entre eux (utilisation du
mot clé VAR dans l’en-tête de la procédure).
ISET CHARGUIA 4
Algorithmique & structures de données 1er Niveau
Exemple :
ALGORITHME principal
VAR
x, y, z : ENTIER
PROCEDURE param ( a : ENTIER ; VAR b : ENTIER ; VAR c : ENTIER)
DEBUT
Écrire (‘ Début de la procédure ‘)
Ecrire (‘ a= ‘, a)
Ecrire (‘ b= ‘, b)
b 2*b
c a+ b
Ecrire (‘ a= ‘, a)
Ecrire (‘ b= ‘, b)
Ecrire (‘ c= ‘, a)
Ecrire (‘ Fin de la procédure’)
FIN param
DEBUT
Ecrire ( ‘ Début du programme Principal’)
x 2
y 4
Ecrire (‘ x= ‘, x)
Ecrire (‘ y= ‘, y)
Param(x, y, z)
Ecrire (‘ x= ‘, x)
Ecrire (‘ y= ‘, y)
Ecrire (‘ z= ‘, z)
Ecrire (‘ Fin du programme’)
Fin principal
Déroulement de l’exécution
2. La récursivité
Définition
Une procédure est dite récursive si elle est définie en partie par elle-même.
La récursivité permet de répéter une suite d’actions. La démarche récursive consiste
à ramener un problème de complexité n à un problème de complexité 1, que l’on sait
résoudre, et un problème de complexité inférieure.
La récursivité est utilisée dans de nombreuses applications telles que la gestion des
listes et des arbres, la recherche opérationnelle et l’intelligence artificielle.
Exercice :
La factorielle est un exemple significatif de récursivité : n != n*(n-1) !
ISET CHARGUIA 5
Algorithmique & structures de données 1er Niveau
Types de récursivité
Récursivité Directe ou Simple
Procédure récursive(…)
Début
<Actions >
récursive(…)
<Actions >
Fin récursive
Récursivité Indirecte ou Croisée
Procédure rec1(…)
Début
<Actions >
rec2(….)
<Actions >
Fin rec1
Procédure rec2(…)
Début
<Actions >
rec1(….)
<Actions >
Fin rec1
Condition d’arrêt
L’appel récursif doit être conditionnel et la condition qui provoque l’appel doit
cesser d’être vraie au bout d’un nombre fini d’appels.
Procédure récursive ( paramètres_formels)
Début
<Actions >
Si condition alors
recursive(paramètres_effectifs)
fsi
<Actions >
Fin récursive
Les paramètres de l’appel et les actions qui le précèdent doivent donc modifier la
valeur de la condition et la rendre fausse au bout d’un nombre fini d’appels. Le
nombre d’appel correspond à la profondeur de la récursivité.
ISET CHARGUIA 6
Algorithmique & structures de données 1er Niveau
Exercice :
Fonction fac ( n : entier) : entier
Début
Écrire (‘ Entrée dans fac’)
Si n=1 alors
fac 1
Sinon
n n* fac(n-1)
fsi
VALRET n
Fin fac
Schéma de fonctionnement d’une procédure ou fonction récursive
A chaque appel de la procédure, son contexte (l’ensemble de ses variables locales et
l’ensemble de ses paramètres) est empilé. Cela comprend :
la valeur de chaque variable locale
la valeur de chaque paramètre d’entrée
la valeur de chaque paramètre de sortie
Avant chaque retour de procédure, le contexte est dépilé.
Comparaison entre les schémas itératif et récursif
Tout programme exprimé sous forme récursive a une forme itérative équivalente et
réciproquement.
Schéma Itératif Schéma récursif
< Init > < Premier Appel>
Tant que NON (test_arrêt) Faire < Début procédure récursive>
< Traitement> Si NON (test_arrêt)
< Progression de cont> Alors
< Traitement>
Ftq Fsi
< Fin procédure récursive>
ISET CHARGUIA 7
Algorithmique & structures de données 1er Niveau
Exemple : La factorielle
1/ Schéma Itératif
FONCTION fact_iter ( n : entier) : entier
VAR
nb, cpt : entier
DEBUT
cpt n
nb 1
Tant que ( cpt <> 0) Faire
nb nb * cpt
cpt cpt – 1
Ftq
VALRET n
Fin fact_iter
2/ Schéma Récursif
Fonction fac_rec ( n : entier) : entier
Début
Écrire (‘ Entrée dans fac’)
Si n=1 alors
fac 1
Sinon
n n* fac(n-1)
fsi
VALRET n
Fin fac_rec
ISET CHARGUIA 8
