DÉPARTEMENT MATH ET
INFORMATIQUE
Algorithmique II
Pr. SADIQ Mounir
2023-2024
Numérique Récursivité
Dans la vie de tous les jours :
3
Notion de récursivité
• Lorsque la définition d'un objet fait appel à l'objet
lui même, on parle de définition récursive.
• On rencontre souvent cette notion de récursivité :
– Dans la vie de tous les jours
– En mathématiques
– En informatique
4
En mathématiques
• les suites définies par récurrence.
• un puissant moyen de démonstration par
récurrence.
5
En informatique
Définition: On appelle récursive toute fonction ou procédure qui
s’appelle elle même.
Objectif: la récursivité consiste à prendre un problème et à le
résoudre en utilisant ses versions les plus simples.
Comment ?
6
Exemple : Calcul de la somme des N premiers naturels:
la fonction Addition (N)
Comment on peut résoudre ce problème d’une manière récursive?
5 étapes pour résoudre n’importe quel problème récursif
7
Conception d’une solution récursive
• Etape 1: quel est l’entrée la plus simple possible pour la fonction, c’est-à-
dire le cas où la fonction peut nous donner une réponse explicite.
•
exemple: le cas de la fonction Addition (N):
N=1 on a un seul entier qui vaut 1 donc:
Addition (1)1
cas de base
8
Conception d’une solution récursive
• Etape 2: utiliser des exemples et visualiser les
entrées et les sorties de la fonction
N=3 N=4
N=2
N=1
1 1+2 1+2+3
1+2+3+4
9
Conception d’une solution récursive
• Etape 3: essayer de trouver la relation entre les
exemples Est-ce
les qu’on
pluspeut
grands avec les exemples
relier Addition(4) avec Addition (3)
petits
Est-ce qu’on peut relier Addition(3) avec Addition (2)
Est-ce qu’on peut relier Addition(2) avec Addition (1)
N=1 N=2 N=3 N=4
1+2
1+2+3
1+2+3+4
10
Conception d’une solution récursive
• Etape 4: généraliser le modèle
+
=
k
11
Addition (k) Addition (k-1)
Conception d’une solution récursive
Etape 5: combiner le modèle récursif avec le cas de base
Si N=1
S=1
Addition (N) =
Sinon
S=N+Addition (N-1)
Algorithme récursif: La traduction de la formule de récurrence est :
Fonction Addition (N : entier) : entier ENTRER N
def add(n):
Si (N = 1) Alors si N=1 alors
if n==1:
s 1 s= 1
s=1
Sinon sinon
else:
s N + Addition(N - 1)) s= N+Addition(N-1)
s=n+add(n-1)
Fin Si finsi
return s
Retourner s retourner s
print(add(5))
FinFonction Ecrire Addition(5)
Ecrire(Addition(5))
12
Simulation
Addition (5) Addition (4) Addition (3)
5+Addition (4) 4+Addition (3) 3+Addition (2)
5+10=15 4+6 =10 3+3=6
Addition (2)
Addition (1)
2+Addition (1) 1
2+ =3 13
Cas d’arrêt
Une fonction récursive doit toujours
comporter une condition de fin des
appels, pour ne pas avoir une exécution
infinie.
14
La condition d’arrêt
Comme dans le cas d’une boucle, il faut un cas d’arrêt où l’on ne fait pas
d’appel récursif.
procédure récursive(paramètres)
si TEST_D’ARRET alors
instructions du point d’arrêt
sinon
instructions récursive(paramètres changés) // appel récursif
15
La condition d’arrêt
Fonction Addition (N : entier) : entier
Début
Si (N = 1) Alors La condition d’arrêt
Retourne (1)
Sinon
Retourne (N + Addition(N - 1)) Appel récursif
Fin Si
Fin
une variable de contrôle : entier naturel qui doit :
- décroître strictement à chaque appel récursif ;
- sa valeur finale mène à des cas de base.
16
Evolution d’un appel récursif
Fonction Addition (N : entier) : entier
Si (N = 1) Alors
s 1
Sinon
s N + Addition(N - 1))
Fin Si
Retourner s
FinFonction
Ecrire(Addition(4)
Pour N = 4, calculons Addition(4)
Addition(4) = 4 + Addition(3) = 10
Addition(3) = 3 + Addition(2) =6
Addition(2) = 2 + Addition(1) =3
Addition(1) =1
17
Algorithme récursif
• Un algorithme est dit récursif quand sa mise en œuvre
utilise ce même algorithme.
Savoir exprimer le problème de taille n en
fonction du même problème de taille inférieur.
• Pour être validé, cet algorithme doit impérativement
vérifier les 2 contraintes de terminaison :
existence d’un ou plusieurs cas de base (condition d’arrêt)
où l’algorithme est directement effectif ;
assurance qu’il n’y aura qu’un nombre fini d’appels
récursifs avant de déboucher sur un cas de base. Cette
assurance est fournie par une variable de contrôle
18
Exercice
En utilisant la propriété : x n = [Link]−1 (lorsque n > 0) et x 0 = 1,
écrire :
une fonction qui calcule x n (où x et n sont des entiers),
en utilisant la récursion.
def puissance(x,n):
if n==0:
Fonction puissance (x,n : entier) : entier return 1
Si (n = 0) Alors else:
p 1 return x *puissance(x,n-1)
Sinon print(puissance(2,3))
p x *puissance(x,n-1)
Fin Si ENTRER x,n
Retourner p si n=0 alors
FinFonction p=1
Ecrire(puissance(2,3)) sinon
p=x*puissance(x,n-1)
finsi
retourner p
Ecrire puissance(2,3)
Type de récursivité
La récursivité terminale
La récursivité non terminale
20
Type de récursivité: récursivité terminale
On dit qu’une fonction est récursive terminale,
si aucun traitement n’est effectué à la
remontée d’un appel récursif sauf le retour
d’un résultat:
21
Type de récursivité: récursivité
terminale
• Exemple: Algorithme reste de la division
A = Bq + r où (q, r) ∈ N2 et r < B
• Tant qu'il nous reste dans A une quantité
suffisante pour prendre B, on retranche B de A,
c'est-à-dire qu'on prend une fois de plus B de A.
• Lorsqu'on ne peut plus retrancher B de A (parce
que A < B) alors le reste de la division euclidienne
c'est A.
22
• Exemple: Algorithme reste de la division
A = Bq + r où (q, r) ∈ N2 et r < B
• Cas de base:
Si A < B alors le reste de la division
euclidienne c'est A
23
Type de récursivité: récursivité
terminale
• Exemple: Algorithme reste de la division
• A=13 et B=4
– A=A-B Reste =1
A=9 et B=4
A=5 et B=4
A=1 et B=4
Reste =1
24
Type de récursivité: récursivité
terminale
• Définition récursive de la fonction reste par
des équations:
• (1) reste(A, B) = A quand A < B
• (2) reste(A,B) = reste(A − B, B) quand A ≥ B
Fonction Rest (A : entier, B: entier) : entier
ENTRER A,B Debut
si A<B alors Si (A<B) Alors
r=A Retourne (A)
sinon Sinon
r=rest(A-B,B) Retourne (Rest (A-B, B)
finsi Fin Si
retourner r Finfonction
ecrire rest(13,4) ecrire (rest(13,4))
25
Type de récursivité: la récursivité terminale
ENTRER A,B
Fonction Rest (A : entier, B: entier) : entier
si A<B alors
Debut
r=A
Si (A<B) Alors
sinon
Retourne (A)
r=rest(A-B,B)
Sinon
finsi
Retourne (Rest (A-B), B)
retourner r
Fin Si
ecrire rest(13,4)
Fin
calculons Rest(13,4)
Rest(13,4)
def Rest(A,B):
Rest(9,4) if A<B:
return A
Rest(5,4) else:
return Rest(A-B,B)
Rest(1,4) = 1
print(f(13,4))
26
Type de récursivité: récursivité terminale
On dit qu’une fonction est récursive terminale, si aucun traitement
n’est effectué à la remontée d’un appel récursif sauf le retour d’un
résultat.
la valeur retournée est directement la valeur obtenue par un appel
récursif, sans qu’il n’y ait aucune opération sur cette valeur.
Il n’y a ainsi rien à retenir sur la pile Cette forme de récursivité
est bénéfique pour la gestion de l'espace mémoire de la fonction.
27
Type de récursivité: la récursivité
non terminale
• Un module récursif est dit non terminal si le
résultat de l’appel récursif est utilisé pour
réaliser un traitement (en plus du retour du
module).
28
Evolution d’un appel récursif
Fonction Addition (N : entier) : entier
def Addition(N):
Si (N == 1) Alors:
if N == 1:
Retourne 1
return 1
Sinon
else:
Retourne N + Addition(N - 1)
return N+Addition(N-1)
Fin Si
Fin
print(Addition(4))
Pour N = 4, calculons Addition(4)
Addition(4) = 4 + Addition(3) = 10
Addition(3) = 3 + Addition(2) =6
Addition(2) = 2 + Addition(1) =3
Addition(1) =1
29
la récursivité non terminale récursivité terminale
