La récursivité
CHAPITRE I:
1
La récursivité
1. Introduction
La récursivité fournit un moyen simple et propre d’écrire du code. C' est un concept général
qui peut être illustré dans quasiment tous les langages de programmation, et qui peut être utile
dans de nombreuses situations.
L’objectif de ce premier chapitre est de faire un rappel sur les sous-programmes puis
d’introduire la notion de récursivité et enfin de présenter ses différents types.
2. Les sous-programmes
2.1. Définition d'un sous-programme
Les sous-programmes (fonctions et procédures) offrent au programmeur le moyen de
réaliser des modules de programmation dans le cas où une même suite d'instructions utilisant
les mêmes données doit être écrite plusieurs fois. Ces derniers sont relativement
indépendants, réalisant chacun une tâche parfaitement définie, et pouvant être développés,
vérifiés et testés séparément.
Une fois écrit et mis au point, un sous-programme pourra être vu et utilisé comme une ‘’boîte
noire'', dont on n'aura à connaître que le nom (symbolisant le calcul réalisé), et les paramètres
d'entrée et de sortie.
2.2. Les paramètres
Un paramètre est une donnée manipulée par une section de code. Nous pouvons
logiquement distinguer trois genres de paramètres :
1. Les paramètres d'entrée, qui représentent des valeurs nécessaires au calcul effectué par le
sous-programme ;
2. Les paramètres de sortie, qui désignent les variables où devront être rangées les résultats
du calcul ;
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
3. Les paramètres mixtes, qui désignent des variables dans lesquelles se trouvent initialement
des données nécessaires au calcul, et dont le contenu modifié par le calcul constituera un
2
résultat.
2.3. Passage de paramètres
Les paramètres d'un sous-programme servent à l'échange des informations entre les
sous-programme et l'extérieur, plus précisément le contexte d'où elle est appelée.
Les paramètres d’un sous-programme sont dits paramètres formels. Les paramètres de l'appel
du sous-programme sont dits paramètres effectifs.
Lors de l'appel du sous-programme, la correspondance est faite entre les paramètres
de l'appel (les paramètres effectifs) et les paramètres du sous-programme (les paramètres
formels).
2.4. Différence entre les fonctions et les procédures
Ils existent deux types de sous-programmes ; les procédures et les fonctions dont les
différences sont résumées dans le tableau suivant :
Fonction Procédure
Elle ne possède que des paramètres d’entrée Une procédure peut avoir des paramètres
d’entrée et de sortie ou d’entrée/sortie
Elle ne peut communiquer qu’un seul résultat Elle peut communiquer de 0 à plusieurs
à travers le nom de la fonction résultats à travers des paramètres de sortie
Une fonction s’appelle à l’intérieur d’une L’appel à la procédure est une instruction en
instruction qui utilise la valeur retournée par elle même
la fonction
2.5. Exercice d’application
Ecrire un algorithme permettant de calculer : 𝑃 = 1𝑛 + 2𝑛 + 3𝑛 + ⋯ + 𝑖 𝑛 (avec i et n deux
entiers positifs).
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
3
Algorithme Calcul ;
Var j, i,n, p : entier ;
Fonction Puissance (k, m : entier) : entier ;
Var i , puis : entier ;
Début
Si (m=0) Ou (k=1) Alors
Puissance ← 1 ;
Si (k=0) Alors
Puissance ← 0 ;
Sinon
Puis ← 1 ;
Pour i allant de 1 à m Faire
Puis ← Puis × k ;
Fin ;
Puissance ← Puis ;
Fin ;
Fin ;
Fin ;
Début {PP}
Lire (i,n),
P← 0;
Pour j allant de 1 à i Faire
P ← P+Puissance (j,n) ;
Fin ;
Fin .
3. Les Sous-programmes récursifs
3.1 Définition d'un sous-programme récursif
Un sous-programme est dit récursif si durant son exécution, il fait appel à lui même pour
continuer son exécution. Chaque appel à la fonction est indépendant des autres, avec ses
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
propres variables. Dans ce cas, la solution du problème général demande la résolution de
plusieurs sous-problèmes particuliers qui sont semblables au premier problème.
4
L'exemple le plus classique d'emploi de la récursivité est l'écriture de la fonction factorielle.
Pour rappel, la factorielle d'un nombre n est définie comme n fois la factorielle du
nombre n-1, et la factorielle de 1 est 1. Ainsi, pour résoudre le problème « combien vaut la
factorielle de 4 ?», il faut résoudre le problème « combien vaut la factorielle de 3 ?»…etc.
La récursivité est un domaine très intéressant de l'informatique, un peu abstrait, mais très
élégant; elle permet de résoudre certains problèmes d'une manière très rapide, alors que si on
devait les résoudre de manière itérative, il nous faudrait beaucoup plus de temps et de
structures de données intermédiaires.
La récursivité utilise toujours la Pile d’exécution du programme en cours qui est un
emplacement mémoire destiné à mémoriser les paramètres, les variables locales ainsi que
l’adresse de retour de chaque fonction en cours d’exécution. En effet, dans une procédure
récursive, toutes les variables locales sont stockées dans la pile, et empilées autant de fois
qu'il y a d'appels récursifs. Ces variables seront par la suite désempilées. La pile fonctionne
selon le principe LIFO (Last-In-First-Out) et elle a une taille fixée (une mauvaise utilisation
de la récursivité peut entraîner un débordement de pile).
3.2 Ecriture d’un sous-programme récursif
Pour écrire un sous-programme récursif, il faut que le problème que l'on doit
résoudre se prête bien à l'utilisation d'un sous-programme récursif.
Tout sous-programme récursif comporte une instruction (ou un bloc d'instructions) nommée
"point terminal" ou "point d'appui" ou "point d'arrêt", qui indique que le reste des instructions
ne doit plus être exécuté.
La structure très nette des problèmes propres à la récursivité (un problème = un ou plusieurs
sous-problèmes) permet de présenter une manière générale d'écrire des sous-programmes
récursifs :
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
1. D'abord, il faut gérer le cas simple, c'est-à-dire celui qui ne nécessite pas de rappeler
récursivement le sous-programme. Pour la factorielle, c'est le cas où n vaut 1 (car on
5
sait directement que 1! = 1).
2. Ensuite, il faut gérer le ou les sous-problèmes récursifs, en rappelant le sous-
programme récursif pour chaque sous-problème à résoudre.
3.3 Différence entre les fonctions et procédures récursives
La seule différence qui existe entre les fonctions et les procédures récursives réside dans la
manière dont ce fait l’appel. Nous allons voir dans ce qui suit quelques exemples classiques
de fonctions et procédures récursives :
Exemple 1 : calcul de la factorielle
1 𝒔𝒊 𝑛 = 0 𝑜𝑢 𝑛 = 1
𝑛! = {
𝑛 × (𝑛 − 1)! 𝒔𝒊𝒏𝒐𝒏
L'algorithme correspondant est le suivant:
Fonction Fact (n :entier) : entier ;
Début
Si (n=0) ou (n=1) Alors
Fact 1 ;
Sinon
Fact n × Fact (n-1);
Fin;
Fin;
Déroulement:
XFact(4)
4×Fact(3)
24
3×Fact(2)
24 2×Fact(1)
6 1
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
6
Exemple 2 : calcul du nombre d’occurrences d’une valeur donnée dans un tableau
d’entiers
L'algorithme correspondant est comme suit:
Algorithme Calcul ;
Type Tab= Tableau [1..10] d’entiers ;
Var A : Tab ;
i, n, Nbre, Val : entier ;
Procédure Occurrence (A : Tab ; Var Nbre : entier ; i, n, val : entier) ;
Début
Si (i≤n) Alors
Si (A[i]=Val) Alors
Nbre Nbre+ 1;
Fin;
Occurrence (A, Nbre, i+1, n, val) ;
Fin;
Fin;
Début {PP}
Lire (n) ;
Pour i allant de 1 à n Faire
Lire (A[i]) ;
Fin ;
Lire (val) ;
Nbre 0;
i 1;
Occurrence (A, Nbre, i, n, val) ;
Ecrire(Nbre) ;
Fin;
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
Déroulement:
Soit le tableau A suivant:
7
5 12 14 12 7
On cherche le nombre d'occurrences de la valeur 12 dans le tableau A:
Occurrence (A, 0, 1, 5, 12)
Occurrence (A, 0, 2, 5, 12)
Occurrence (A, 1, 3, 5, 12)
Occurrence (A, 1, 4, 5, 12)
Occurrence (A, 2, 5, 5, 12)
Occurrence (A, 2, 6, 5, 12)
2
4. Types de récursivité
4.1 Récursivité simple : c'est une récursivité dans laquelle on trouve un seul appel
récursif.
Exemple :
Soit la fonction Puissance (x,n). Cette dernière peut être définie récursivement comme
suit :
1 𝒔𝒊 𝑛=0
𝑋𝑛 = {
𝑥 × 𝑥 𝑛−1 𝒔𝒊 𝑛≥1
L’algorithme correspondant est :
Fonction Puissance (x, n :entier) : entier ;
Début
Si (n=1) Alors
Puissance 1 ;
Sinon
Puissance 𝑥 × Puissance(x,n-1);
Fin;
Fin;
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
4.2 Récursivité multiple : C’est une récursivité contenant plus d’un appel récursif.
𝑝
8
Exemple : Calcul des combinaisons (𝐶𝑛 ) en utilisant la relation de Pascal.
𝑝 1 𝒔𝒊 𝑝 = 0 𝒐𝒖 𝑝 = 𝑛
𝐶𝑛 = { 𝑝 𝑝−1
𝐶𝑛−1 + 𝐶𝑛−1 𝒔𝒊𝒏𝒐𝒏
L’algorithme correspondant est :
Fonction Pascal ( n , p :entier) : entier ;
Début
Si (p=0) Ou (p=1) Alors
Pascal 1 ;
Sinon
Pascal Pascal(n-1,p)+ Pascal(n-1,p-1);
Fin;
Fin;
4.3 Récursivité mutuelle : Des fonctions sont dites mutuellement récursives si elles
dépendent les unes des autres.
Exemple : Définition de la parité.
𝑉𝑟𝑎𝑖 𝒔𝒊 𝑛 = 0 𝐹𝑎𝑢𝑥 𝒔𝒊 𝑛 = 0
Pair (n) = { Impair (n) = {
𝐼𝑚𝑝𝑎𝑖𝑟 (𝑛 − 1) 𝑺𝒊𝒏𝒐𝒏 𝑃𝑎𝑖𝑟 (𝑛 − 1) 𝑺𝒊𝒏𝒐𝒏
Les algorithmes correspondant sont :
Fonction Pair ( n :entier) : Booléen; Fonction Impair ( n :entier) : Booléen;
Début Début
Si (n=0) Alors Si (n=0) Alors
Pair Vrai ; Impair Faux ;
Sinon Sinon
Pair Impair(n-1); Impair Pair(n-1);
Fin; Fin;
Fin; Fin;
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
4.4 Récursivité imbriquée : Dans ce type de récursivité, les paramètres du sous- 9
programme récursif sont eux-mêmes récursifs.
Exemple : Fonction d’Ackermann
Cette fonction est définie comme suit :
𝑛+1 𝒔𝒊 𝑚 = 0
𝐴(𝑚, 𝑛) = { 𝐴(𝑚 − 1,1) 𝒔𝒊 𝑚 > 0 𝑒𝑡 𝑛 = 0
𝐴(𝑚 − 1, 𝐴(𝑚, 𝑛 − 1)) 𝑺𝒊𝒏𝒐𝒏
L’algorithme correspondant est :
Fonction Ackermann ( m , n:entier) : entier ;
Début
Si (m=0) Alors
Ackermann n+ 1 ;
Sinon
Si ( 𝑚 > 0) 𝑒𝑡 (𝑛 = 0) 𝐀𝐥𝐨𝐫𝐬
Ackermann Ackermann (𝑚 − 1,1);
Sinon
Ackermann Ackermann (m-1, Ackermann(m,n-1));
Fin;
Fin;
Fin;
5. Récursivité terminale et Récursivité non terminale
5.1 Récursivité terminale
Un algorithme est dit récursif terminal s’il ne contient aucun traitement après un
appel récursif. C’est une récursivité dont l’appel récursif est la toute dernière
instruction réalisée. En d’autres termes, aucun traitement n’est effectué à la
remontée d’un appel récursif sauf le retour de la valeur.
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
Exemple :
10
Fonction Fact1 (n, Resultat : Entier) : Entier ;
Début
Si (n>1) Alors
Fact1 (n-1, n×Resultat) ;
Fin ;
Fin ;
Avec l'appel initial : 'Fact1 (n, 1)'
5.2 Récursivité non terminale
Un algorithme est dit récursif non terminal s’il contient un traitement après un
appel récursif.
Exemple :
Fonction Fact2 (n : Entier) : Entier ;
Début
Si (n=1) Alors
Fact2 1;
Sinon
Fact2 n× Fact2 (n-1) ;
Fin ;
Fin ;
Au lancement de la fonction, on aura :
- Une descente récursive (mémoriser les opérations à faire jusqu’à la condition
d’arrêt),
- Condition terminale,
- Une remontée récursive (Réaliser les opérations en partant de la condition
d’arrêt).
6. Conclusion
La récursivité permet de réduire un problème à sa plus petite forme pour simplifier la
solution. L’avantage de la récursivité est qu’elle se situe à un niveau d’abstraction
supérieur par rapport à l’itération. Une solution récursive décrit comment calculer la
solution à partir d’un cas plus simple. Au lieu de préciser chaque action à réaliser, on décrit
ce qu’on veut obtenir (c’est ensuite au système de réaliser les actions nécessaires pour
obtenir le résultat demandé).
Dr KHAMTACHE-KHOULALENE Nadjet
La récursivité
Souvent la solution récursive d’un problème est plus intuitive que celle itérative et le
programme à écrire est plus court et plus lisible. Cependant, elle est moins efficace que 11
l’itération, car la répétition est réalisée par des appels successifs de fonctions, ce qui est
plus lent que l’incrémentation d’un compteur de boucle. Dans les langages qui offrent à la
fois l’itération et la récursivité, on va préférer la récursivité surtout dans les situations où la
solution itérative est difficile à obtenir, par exemple :
si les structures de données manipulées sont récursives (ex. les arbres).
si le raisonnement lui même est récursif.
Néanmoins, il est à noter qu'un programme récursif a besoin de plus d'espace qu'un
programme itératif, car toutes les fonctions resteront dans la pile jusqu'à ce que le cas de
base soit atteint. En outre, le temps requis est plus long en raison d'appels de fonction.
Dr KHAMTACHE-KHOULALENE Nadjet
