Récursivité

Ecole Supérieure en Sciences et Technologies
de l’Informatique et du Numérique
Chapitre III: La Récursivité
Algorithmique et Structures de
Données Dynamiques
1re année Ecole Prépa. De l’ESTIN de Bejaia
Année: 2020-2021
Définition
 Qu’est ce que la récursivité?
Une fonction est dite récursive si elle est définie par elle même.
Une fonction récursive doit toujours définir un cas simple (dit trivial
ou d’arrêt), et un cas général (ou récursif).
La fonction récursive doit pouvoir terminer son exécution par son

cas trivial.
2
Définition
Une fonction récursive est définie par :
 au moins un cas de base et,
 au moins un cas général.
— Cas de base: on décrit les cas pour lesquels le résultat de la fonction

est simple à calculer : la valeur retournée par la fonction est
directement définie.
— Cas général: la fonction est appelée récursivement et le résultat

retourné est calculé en utilisant le résultat de l'appel récursif. A
chaque appel récursif, la valeur d'au moins un des paramètres
(effectifs) de la fonction doit changer.
3
 Exemple 1: La factorielle
Soit la fonction mathématique ‘factorielle’ définie pour tout entier
positif n comme suit :
𝟏 𝒔𝒊 𝒏 = 𝟎
𝐧! =
𝒏∗ 𝒏−𝟏 ! 𝒔𝒊 𝒏 > 𝟎
Cette fonction, comme nous pouvons le remarquer, se définie par
elle-même. Elle envisage le cas trivial où n = 0, et pour lequel 0! = 1,
et définie les valeurs de n! comme étant le produit de n et de (n -1)!.
En effet, si l’on souhaitait calculer 4! par exemple, il nous suffirait de
multiplier 4 par 3!, et donc devoir calculer 3!, et ainsi de suite. C’est à
dire :
4! = 4 * 3!
= 4 * (3 * 2!)
= 4 * (3 * (2 * 1!))
= 4 * (3 * (2 * (1 * 0!)))
= 4 * (3 * (2 * (1 * 1))) = 24. 4
L’algorithme itératif de la factorielle:
{Version itérative de la fonction factorielle}
Fonction Fact ( n : Entier) : Entier
Var i : Entier
Début
Fact ← 1
Pour i allant de 1 à n faire
Fact ← Fact*i
FinPour
Fin
5
L’algorithme récursif de la factorielle:
{Version récursive de la fonction factorielle}

Fonction Factorielle( n : Entier) : Entier
Début
Si (n = 0) Alors
Factorielle ← 1
Sinon
Factorielle ← n*Factorielle(n-1)
FinSi
Fin
Remarquez que la fonction factorielle s’appelle elle-même jusqu’à
ce qu’elle finisse par le cas trivial 0!.
6
 Exemple 2: La Suite de Fibonnacci
Le mathématicien italien Leonardo Fibonnacci, a définie la suite qui
porte son nom comme suit :
𝟏 𝒔𝒊 𝒏 < 𝟐
𝐅𝐢𝐛(𝐧) =
𝑭𝒊𝒃 𝒏 − 𝟏 + 𝑭𝒊𝒃 𝒏 − 𝟐 𝒔𝒊 𝒏 ≥ 𝟐
Comme nous pouvons le constater, la fonction Fib a un cas trivial ;

celui où n est inférieur à 2, et un cas général pour n supérieur ou égal
à 2.
Par exemple:
Fib(4) = Fib(3) + Fib(2)
= (Fib(2) + Fib(1)) + (Fib(1) + Fib(0))
= ((Fib(1) + Fib(0)) + Fib(1)) + (Fib(1) + Fib(0))
= ((1 + 1) + 1) + (1 + 1) = 5
7
L’algorithme itératif de la suite de Fibonnacci:
{Version itérative de la fonction de suite de Fibonnacci}
Fonction Fibo ( n : Entier) : Entier
Var x,y,U : Entier
Début
x←1
y←1
Pour i allant de 2 jusqu’à n faire
U ← x+y
x←y
y←U
FinPour
Fibo ← U
Fin
8
L’algorithme récursif de la suite de Fibonnacci:
{Version récursive de la fonction de suite de Fibonnacci}
Fonction Fib ( n : Entier) : Entier
Début
Si (n < 2) Alors
Fib ← 1
Sinon
Fib ← Fib(n-1)+Fib(n-2)
FinSi
Fin
9
 Règles de la récursivité
La récursivité facilite la résolution de problèmes complexes. Il est
souvent plus facile d’exprimer la solution à un problème donné avec
des sous-solutions similaires à celle que l’on recherche et qui se
terminent par des cas triviaux faciles à exprimer sans récursivité.
Pour concevoir des algorithmes récursifs, nous devons prendre en

considération les trois règles suivantes :
1) Une fonction récursive doit retourner un résultat pour toute
entrée valide.
2) Une fonction récursive doit définir un cas trivial qui n’effectue
aucun appel récursif.
3) Les appels récursifs devraient être de plus en plus simples, et
conduire au cas trivial.
10
 Exemple 3: Palindrome
Une chaine de caractères est un palindrome si on peut la lire de gauche
à droite, ou de droite à gauche, de la même façon. Nous donnons
comme exemple les palindromes suivants:
— “radar’’
— “malayalam’’
— “ressasser’’
— “été’’
— “laval’’
— “ici’’
— “elle’’
Pour vérifier si une chaine de caractères est un palindrome, il suffit de
voir si les deux caractères à ses deux bouts sont égaux, et que la chaine
de caractères entre ces deux bouts est elle-même un palindrome.
11
Pour vérifier si le mot ‘ressasser’ est un palindrome, nous suivons les
étapes suivantes :
Après avoir vérifié si

les deux caractères
aux extrémités sont
égaux (‘r’ = ‘r’), nous
vérifierons si la partie
restante de la chaine
"ssass" est un
palindrome, et ainsi
de suite.
12
Devoir de maison :
Écrivez la fonction EstPalaindrome qui prend une chaine de
caractères et sa taille en entrée, et renvoie vrai si c’est un
palindrome, ou faux sinon.
13
Récursivité Directe et Indirecte
Lorsqu’un sous-programme fait appel à lui même, comme dans le cas de
la factorielle, on appelle cela récursivité directe.
Parfois, il est possible qu’un sous-programme A fasse appel à un sous-
programme B, qui lui même fait appel au sous-programme A. Donc
l’appel qui part de A atteint de nouveau A après être passé par B,
s’appelle récursivité indirecte (récursivité croisée).
 Exemple 4:
Un exemple de récursivité indirecte est la définition récursive des
nombres pairs et impairs. Un nombre n positif est pair si n-1 est impair,
un nombre n positif est impair si n-1 est pair. Les conditions d’arrêt
sont données par les valeurs n=0, qui est pair et n=1, qui est impair.
14
Récursivité Indirecte:
{Version récursive des Nombres Pairs} {Version récursive des Nombres Impairs}
Fonction Pair ( N : Entier) : Booléen Fonction Impair ( N : Entier) : Booléen
Début Début
Si (N = 0) Alors Si (N = 0) Alors
Retourner vrai Retourner Faux
Sinon Sinon
Si (N=1) Alors Si (N=1) Alors
Retourner Faux Retourner Vrai
Sinon Sinon
Retourner Impair(n-1) Retourner Pair(n-1)
FinSi FinSi
FinSi FinSi
Fin Fin
15
La Récursivité
 Exercice 1:
1)- Écrire une fonction récursive qui renvoie le reste de la division
euclidienne d'un entier a par un entier b en utilisant les soustractions
successives.
2)- Ecrire une fonction récursive qui calcule la somme des n premiers
entiers ( S = 1+2+3+ … +(n-1)+n)
3)- Ecrire une fonction récursive qui permet de chercher une valeur
dans un tableau trié en utilisant la recherche Dichotomique.
16
La Récursivité
 Solution :
Fonction RestDiv (a,b : Entier): Entier

Début
Si ( a < b ) Alors
RestDiv ← a
Sinon
RestD ← RestD(a-b, b)
FinSi
Fin
17
La Récursivité
 Solution :
Fonction Somme_Rec (n : Entier) : Entier
Début
Si ( n < 1 ) Alors
Retourner 0
Sinon
Si (n = 1) Alors
Retourner 1
Sinon
Retourner (Somme_Rec(n-1) + n)
FinSi
FinSi
Fin
18
La Récursivité
 Solution :
Fonction RechercheD (n : Entier, T: Tableau [1..30] d’entiers, a, b : Entier) : Booléen
Var c : Entier
Début
Si ( a > b ) Alors
retourner Faux
Sinon
c ← (a + b)/2
Si (T[c] = n) Alors
retourner Vrai
Sinon
Si (T[c] < n) Alors
retourner RechercheD(n, T, c+1, b)
Sinon
retourner RechercheD(n, T, a, c-1)
FinSi
FinSi
FinSi
Fin
19
La Récursivité
 Exercice 2:
Fonction récursive d'Ackermann
Soit f la fonction de N×N dans N définie par :
𝑚+1 𝑠𝑖 𝑛 = 0
f n, m = 𝑓 𝑛 − 1,1 𝑠𝑖 𝑚 = 0 𝑒𝑡 𝑛 ≥ 1
𝑓 𝑛 − 1, 𝑓(𝑛, 𝑚 − 1) 𝑠𝑖 𝑚 ≥ 1 𝑒𝑡 𝑛 ≥ 1
1. Calculer f(1, 0); f(2, 0) et f(3, 0):

2. Ecrire une fonction Ackermann qui calcule les valeurs de f.
20
La Récursivité
 Solution :
Fonction Ackermann( m,n : Entier) : Entier
Début
Si ( n = 0 ) Alors
Retourner m+1
Sinon
Si (m = 0) Alors
Retourner Ackermann(n-1,1)
Sinon
Retourner Ackermann(n-1, Ackermann(n,ms-1))
FinSi
FinSi
Fin
21
Notions d’appel à une fonction
Soit un registre d’instruction qui pointe sur l’instruction à exécuter
d’un programme donné. Comment se passe un appel de fonction ?
Sachant que cette fonction appelée est localisée dans une zone
mémoire qui n’est pas forcément adjacente à l’instruction en cours.
Pour comprendre ce mécanisme, étudions l’algorithme abstrait
suivant :
{Appel à une Fonction}
Début {Début du Programme Principal}
{Partie avant appel à func}
…
x←1
y←2
r ← func(x) {Appel à func}
{Partie après appel à func}
…
x←r+y
Fin
22
{Appel à une Fonction}
Début {Début du Programme Principal}
{Partie avant appel à func}
…
x←1 Le programme principal a un
y←2 contexte d’exécution qu’il doit
r ← func(x) reprendre lorsque la fonction
{Partie après appel à func} func lui redonne la main.
…
x←r+y
Fin
Les variables x et y doivent avoir les mêmes valeurs qu’avant l’appel à la
fonction func (si bien sûr la fonction func ne les change pas).
Lors de l’appel à func(x) les valeurs de x et y
sont sauvegardées quelque part et ensuite restaurées à la fin de cet appel.
De même pour les paramètres éventuels qu’aurait eus le programme
principal. 23
Le processus d’appel d’une fonction est le suivant:
{Etapes d’exécution du programme principal}
— Partie avant l’appel à func.
— Sauvegarder les variables et les paramètres du programme
principal.
— Faire passer x à func, et exécuter func.
— Restaurer les variables et les paramètres du programme principal.
— Partie après l’appel à func
Si la fonction func fasse elle-même appel à une autre fonction func2,

en lui passant comme paramètre une variable z. Alors, la fonction
func, s’exécutera comme suit :
24
{Etapes d’exécution de func}

— Partie avant l’appel à func2.
— Sauvegarder les variables locales et les paramètres de func.
— Faire passer z à func2, et exécuter func2.
— Restaurer les variables locales et les paramètres de func.
— Partie après l’appel à func2.
En résumé, si un programme principal fait appel à une fonction func

qui elle-même fait appel à une deuxième fonction func2, les
opérations doivent être exécutées dans l’ordre suivant :
25
{Etapes d’exécution du programme principal}
1. Partie avant l’appel à func.
2. Sauvegarder les variables et les paramètres du programme principal.
3. Faire passer x à func, et exécuter func.
{Etapes d’exécution de func}

4. a). Partie avant l’appel à func2
b). Sauvegarder les variables locales et les paramètres de func.
c). Faire passer z à func2, et exécuter func2.
d). Restaurer les variables locales et les paramètres de func.
e). Partie après l’appel à func
5. Restaurer les variables et les paramètres du programme principal.

6. Partie après l’appel à func.
26
Si nous analysons un peu l’ordre de sauvegarde des variables avant

l’appel et de leurs restauration après, nous remarquerons que les
variables sauvegardées en premier sont les dernières à être
restaurées. Et celles qui sont sauvegardées en dernier sont les
premières à être restaurées
Le principe d’une
PILE
Sauvegarder - - - - - - - - → Empiler
Restaurer - - - - - - - - - - → Dépiler 27
 Adresse de retour
À l’appel d’une fonction, le programme doit savoir où reprendre
l’exécution de la fonction appelante.
En effet, le registre d’instruction ayant été changé, pour pointer sur

le début de la fonction appelée, doit être remis à l’adresse qui suit
cet appel pour que la fonction appelante puisse poursuivre son
exécution.
28
 Adresse de retour
{Appel à une Fonction} A l’appel à la fonction func, le
Début {Début du Programme Principal} registre d’instruction pointe
{Partie avant appel à func} l’opération d’appel r ← func(x).
… Ensuite, la valeur du registre est
x←1
y←2 changée pour pointer le début de
r ← func(x) {Appel à func} la fonction func. Au retour de la
{Partie après appel à func} fonction (après l’exécution de
… func), le registre doit avoir
x←r+y
Fin
l’adresse de l’instruction qui se
trouve juste après l’appel à func.
29
Les Zones de Données
Chaque fonction dispose d’une Zone De Données (ZDD) qui est une
structure (enregistrement) qui inclue :
— Les paramètres avec lesquels cette fonction a été appelée.
— Les variables locales de cette fonction.
— L’adresse de retour vers la fonction qui l’a appelée (fonction appelante).
Appeler une fonction revient donc à:

1- Empiler la Zone De Donnée Courante (ZDDC) dans une pile.
2- Préparer la ZDD de la fonction à appeler.
3- Exécuter la fonction appelée.
4- Retourner à l’adresse de retour.
5- Dépiler une ZDD et la considérer comme ZDDC.
30
Cas Particulier: La Récursivité
Le mécanisme reste le même! Il s’agit d’imaginer “plusieurs copies’’
de cette fonction auxquelles nous faisons appel.
 Exemple : Factorielle
Nous allons détailler la fonction récursive factorielle pour comprendre
ces étapes de sauvegarde et de restauration d’état.
31
Fonction Factoriel( N : Entier) : Entier
Var F, X: Entier
Début
Si (N = 0) Alors La ZDD associée à cette fonction, inclue:
F←1
Sinon — Le paramètre d’appel N.
X ← N-1 — La variable locale X.
F ← Factoriel(X) — L’adresse de retour à l’appelant.
F ← F*N
FinSi La variable F étant retournée, elle
Retourner F n’est pas mise en pile.
Fin
32
Conversion d’algorithmes récursifs en itératifs
Bien que la récursivité est un outil qui nous permet de décrire de

façon simple des solutions à des problèmes complexe, certains
langages ne supportent pas la récursivité (exp. FORTRAN,
COBOL, etc.)
En effet, il est nécessaire de pouvoir convertir un algorithme récursif
en un autre qui soit itératif (donc sans aucun appel récursif). Pour
celà, nous exploitons la notion de Zone De Données (ZDD), en
utilisant notre propre pile.
33
 Etapes de Conversion
Il consiste à reproduire les étapes d’appel vues précédemment.
1) Définir la ZDD : Il s’agit dans cette étape de définir le contenu

d’une ZDD de notre fonction récursive. (Paramètres d’appel,
variables locales, adresse de retour).
2) Définir les points d’appel et de retour: Il faut définir les points (ou
adresses) où la fonction récursive est appelée, et où est-ce qu’elle doit
retourner au programme appelant.
34
 Etapes de Conversion
3) À chaque appel récursif
a. Empiler la ZDD courante (ZDDC).
b. Préparer l’appel, et une ZDD qui contiendrait les paramètres
d’appel, et l’adresse de retour.
c. Se brancher à la fonction pour l’exécuter.
4) Après chaque retour
a. Récupérer l’adresse de retour qui est dans la ZDDC.
b. Dépiler une ZDD (C’est à dire restaurer la ZDD de l’appelant).
c. Se brancher à l’adresse de retour récupérée en (a).
35
 Exemple de Conversion
Pour mieux illustrer les étapes citées ci-dessus, reprenons l’exemple la
factorielle.
1. Définir la ZDD
La structure ZDD contient les éléments suivants :
— Le paramètre d’appel N.
— La variable locale X.
— L’adresse de retour ADR à l’appelant.
Nous devons donc considérer une pile dont les éléments seraient des
ZDDs de ce type.
Pour la conversion de notre algorithme récursif en un algorithme itératif,
nous supposons les variables suivantes :
— ZDDC est la ZDD courante.
— P une pile dont les éléments sont des ZDDs comme celle
définie ci-dessus (donc contient : N, X, et ADR). 36
Exemple de conversion
2. Définir les points de retour
La deuxième étape du procédé de conversion consiste à définir les
points d’appel et de retour de la fonction récursive.
Nous commençons par le point de début de la fonction, le cas trivial.
(L’instruction Si (N=0)), ce point précis de la fonction est important,
puisque c’est ici que nous devons nous brancher à chaque appel.
Appelons donc ce point START. Le point d’appel est clair et
explicité par l’appel récursif.
Quant aux points de retour, nous en avons deux :
— Le point de retour final, situé à l’instruction Retourner F, c’est le
point de retour au programme appelant. Étiquetons ce point par le
label 1.
— Le point de retour de l’appel récursif, situé juste après l’appel
récursif. Étiquetons ce point par le label 2.
37
Var F, X: Entier
Début La ZDD associée à cette fonction, inclue:
Point d’appel Si (N = 0) Alors — Le paramètre d’appel N.
F←1 — La variable locale X.
Sinon — L’adresse de retour à l’appelant.
X ← N-1
F ← Factoriel(X)
Point de retour 1 F ← F*N
FinSi
Retourner F Point de retour final
Fin
38
Var A, F, X : Entier; P : Pile; ZDDC : ZDD
Début
CreerPile(P)
ZDDC.N ← N {Initialiser la Zone De Données Courante}
ZDDC.ADR ← 1 {Point de retour final}
{Start} Si (ZDDC.N = 0) Alors {Début de la fonction convertie}
F←1
A ← ZDDC.ADR {Récupérer l’@ de retour au PA}
ZDDC ← Dépiler(P) {Restaurer la zone de donnée de PA}
Si A = 1 Alors {Gestion du retour}
ALLERA 1{Point de retour final}
Sinon
ALLERA 2
FinSi
… 39
…
Sinon {Gestion de l’appel récursif}
ZDDC.X ← ZDDC.N-1
Empiler(P,ZDDC)
ZDDC.N ← ZDDC.X
ZDDC.ADR ← 2 {adresse de retour}
ALLERA START {appel récursif}
{2} F ← ZDDC.N*F {Point de retour de l’appel récursif}
A ← ZDDC. ADR {Récupérer l’@ de retour au PA}
Si A = 1 Alors {Gestion du retour}
ALLERA 1 Sinon ALLERA 2
FinSi
FinSi
{1} Retourner F {Gestion du retour}
Fin 40
Si vous avez bien remarqué, l’algorithme précédent effectue les dépilement
sans vérifier si la pile est vide. En effet, l’étiquette 1 est branchée après
avoir dépiler toutes les ZDD de la pile.
Nous pouvons donc modifier la séquence du code de gestion de retour

comme suit:
Si PileVide(P) Alors {Gestion du retour}
ALLERA 1
Sinon
ALLERA 2
FinSi
41
Maintenant, nous n’avons plus besoin de sauvegarder l’adresse
de retour puisque nous savons où revenir : Si la pile est vide  retour à (1),
sinon  retour à (2).
Essayons d’améliorer notre algorithme davantage. Si l’on regarde de plus

près l’algorithme récursif de départ : La variable X n’est plus utilisée après
le retour de l’appel à la fonction Factoriel. Donc pourquoi la sauvegarder?
Ce qui nous laisse avec la variable N à sauvegarder et à restaurer. Donc, au
final, une simple pile d’entiers suffit.
Récrivons maintenant une version simplifiée de l’algorithme itératif.
42
Var F, X, ZDDC: Entier; P : Pile
Début
CreerPile(P)
ZDDC ← N {Initialiser la Zone De Données Courante}
{Start} Si (ZDDC = 0) Alors {Début de la fonction convertie}
F←1
ALLERA 1
Sinon
ZDDC ← Dépiler(P) {Réstaurer la zone de donnée de PA}
ALLERA 2
FinSi
…
43
…
X ← ZDDC-1
Empiler(P,ZDDC)
ZDDC ← X
ALLERA START
{2} F ← ZDDC*F {Point de retour de l’appel récursif}
ALLERA 1
Sinon
ZDDC ← Dépiler(P) {Réstaurer la zone de donnée de PA}
ALLERA 2
FinSi
FinSi
Fin
44
Essayons d’améliorer encore l’algorithme en éliminant la variable ZDDC
et la remplacer pas X.
Var F, X: Entier; P : Pile
Début
CreerPile(P)
X ← N {Initialiser X}
{Start} Si (X = 0) Alors {Début de la fonction convertie}
F←1
ALLERA 1
Sinon
X ← Dépiler(P) {Restaurer la zone de donnée de PA}
ALLERA 2
FinSi
…
45
…
Empiler(P,X)
X←X -1
ALLERA START
{2} F ← X*F {Point de retour de l’appel récursif}
ALLERA 1
Sinon
X ← Dépiler(P) {Réstaurer la zone de donnée de PA}
ALLERA 2
FinSi
FinSi
Fin
46
On remarque encore que la séquence de gestion de retours est répété deux
fois pour (X = 0) et (X ≠0)
Var F, X: Entier; P : Pile
Début
CreerPile(P)
X ← N {Initialiser}
{Start} Si (X = 0) Alors {Début de la fonction convertie}
F←1
Empiler(P,X)
X←X -1
ALLERA START
FinSi
… 47
{2} Si PileVide(P) Alors {Gestion du retour}
ALLERA 1
Sinon
X ← Dépiler(P) {Restaurer la zone de donnée de PA}
F ← X*F {Point de retour de l’appel récursif}
ALLERA 2
FinSi
Fin
48
Nous remarquons à ce niveau, que cet algorithme est constitué de 02
boucles qui tournent autours des 02 labels (START) et (2), nous pouvons
alors utiliser une boucle classique comme suit:
{Version itérative de la fonction factorielle} …
Fonction Factoriel( N : Entier) : Entier TantQue Non PileVide(P) Faire
Var F, X: Entier; P : Pile X ← Dépiler(P)
Début F←F*X
CreerPile(P) FinTantQue
F←1
X ← N {Initialiser X} Retourner F
TantQue X ≠ 0 Faire
Empiler(P,X) Fin
X ← X-1
FinTantQue
F←1
….
49
Pour finir, on peut remarquer encore que dans cet algorithme, la 1e boucle
ne fait qu’empiler des entiers allant de N à 1, et la 2e ne fait que les dépiler
allant de 1 à N, tant que la pile n’est pas vide. Nous empilons donc des
valeurs, et quand on termine, nous les dépilons. L’algorithme peut être
simplifié comme suit :
Var X, F : Entier
Début
F←1
Pour X Allant de 1 à N Faire
F←F*X
FinTantQue
Retourner F
Fin
50
ALLERA, ou en anglais, GOTO est une instruction qui

nous permet de sauter à un label (ligne) d’un programme.
En assembleur, son équivalent serait JMP.
51
 Exercice 1:
Soit la fonction récursive suivante:
— Transformer la en Fonction itérative
Fonction PrRec(N : Entier): Entier
Var X, R: Entier
Début
Si ( N = 1 ) Alors
R←1
Sinon
Si (N > 1) Alors
X ← N-1
R ← PrRec(X)
R ← R + (N*N)
FinSi
FinSi
Retourner R
52
Fin
 Exercice 1: Solution
Fonction PrIT( N : Entier) : Entier
Var R, X, ZDDC: Entier ; P : Pile
Début
CreerPile(P)
ZDDC ← N {Initialiser la Zone De Données Courante}
{Start} : Si (ZDDC = 1) Alors {Début de la fonction convertie}
R←1
Si PileVide(P) Alors {Gestion de retour}
ALLERA 1
Sinon
Dépiler(P,ZDDC)
ALLERA 2
FinSi
Sinon
53
 Exercice 1: Solution
Si (ZDDC > 1) Alors
X ← ZDDC-1{Gestion de l’appel récursif}
Empiler(P,ZDDC)
ZDDC ← X
ALLERA START
{2} : R ← (ZDDC * ZDDC )+R {Point de retour de l’appel récursif}
Si PileVide(P) Alors {Gestion de retour}
ALLERA 1
Sinon
Dépiler(P,ZDDC)
ALLERA 2
FinSi
FinSi
Finsi
{1} : Retourner R {Gestion de retour}
Fin
54

Récursivité

Transféré par

Droits d'auteur :

Formats disponibles

Récursivité

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Récursivité

Transféré par

Droits d'auteur :

Formats disponibles

Ecole Supérieure en Sciences et Technologies

Chapitre III: La Récursivité

1re année Ecole Prépa. De l’ESTIN de Bejaia

La fonction récursive doit pouvoir terminer son exécution par son

— Cas de base: on décrit les cas pour lesquels le résultat de la fonction

— Cas général: la fonction est appelée récursivement et le résultat

{Version récursive de la fonction factorielle}

Comme nous pouvons le constater, la fonction Fib a un cas trivial ;

Pour concevoir des algorithmes récursifs, nous devons prendre en

Après avoir vérifié si

Fonction RestDiv (a,b : Entier): Entier

1. Calculer f(1, 0); f(2, 0) et f(3, 0):

Si la fonction func fasse elle-même appel à une autre fonction func2,

{Etapes d’exécution de func}

En résumé, si un programme principal fait appel à une fonction func

{Etapes d’exécution de func}

5. Restaurer les variables et les paramètres du programme principal.

Si nous analysons un peu l’ordre de sauvegarde des variables avant

En effet, le registre d’instruction ayant été changé, pour pointer sur

Appeler une fonction revient donc à:

Bien que la récursivité est un outil qui nous permet de décrire de

Il consiste à reproduire les étapes d’appel vues précédemment.

1) Définir la ZDD : Il s’agit dans cette étape de définir le contenu

Nous pouvons donc modifier la séquence du code de gestion de retour

Essayons d’améliorer notre algorithme davantage. Si l’on regarde de plus

Récrivons maintenant une version simplifiée de l’algorithme itératif.

{1} Retourner F {Gestion du retour}

ALLERA, ou en anglais, GOTO est une instruction qui

Vous aimerez peut-être aussi