0% ont trouvé ce document utile (0 vote)

34 vues141 pages

Introduction à la récursivité en informatique

La récursivité est un concept fondamental en informatique qui permet de résoudre des problèmes en les décomposant en sous-problèmes similaires. Un algorithme récursif s'appelle lui-même, avec une condition d'arrêt pour éviter les appels infinis, comme illustré par les exemples de la factorielle et de la suite de Fibonacci. La compréhension de la récursivité est essentielle pour la programmation et la résolution efficace de problèmes complexes.

Transféré par

derdour amira

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

34 vues141 pages

Introduction à la récursivité en informatique

Transféré par

derdour amira

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

UNIVERSITE ABDELHAMID IBN BADIS MOSTAGANEM

FACULTE DES SCIENCES EXACTES ET DE L’INFORMATIQUE

DEPARTEMENT DE MATHEMATIQUES ET INFORMATIQUE

La récursivité

Cours 2 ASD
Concept de récursivité
 Le concept de récursivité est un concept essentiel
en informatique

 C’est à la fois :
 Une manière d’aborder certains problèmes
 Une méthode de programmation

M Abid 2
Décomposition d’un problème
 L'analyse d'un problème passe souvent par la
décomposition de ce dernier en plusieurs sous-
problèmes.
 Ces sous-problèmes peuvent également être
décomposés à leur tour en sous-problème jusqu'à
un niveau d'opérations élémentaires faciles à
réaliser
 Exemple :
Le principe des fonctions en programmation
qui représentent la réalisation d'une sous
partie d'un problème.

M Abid 3
Décomposition récursive
 Dans certains cas, le sous-problème est une
illustration du problème initial, mais pour un cas
“plus simple”.
 Par conséquent, la solution du problème s’exprime
par rapport à elle-même
 Définition:
On appelle récursive toute fonction ou procédure
qui s’appelle elle-même.
 mathématiques : récurrence
 informatique : récursivité

M Abid 4
Récursivité et récurrence
 Le concept de récursivité se retrouve en
mathématiques sous le terme de récurrence
 De nombreuses définitions mathématiques sont
récurrentes
 Exemple:

Définition récurrente d’un entier naturel:

(i) 0 est un entier naturel
(ii) Si N est un entier naturel N + 1 est aussi
un entier naturel

M Abid 5
Exemple de la factorielle
 Définition par récurrence de la fonction
factorielle
N! = N x (N-1) x …x 1

(i) 0! = 1
(ii) Pour N entier naturel (N > 0)
N! = N×(N - 1)!

M Abid
Exemple de la factorielle
 Définition récurrente de la fonction factorielle:
N! = (1 x 2 x … x (N-1)) x N
N!=(N-1)! x N
 Pour calculer N!, il suffit donc de savoir calculer
(N-1)!
 Le sous-problème du calcul de (N-1)! est le même
que le problème initial mais pour un cas « plus
simple » puisque N-1 < N

M Abid 7
Exemple de la suite de Fibonacci
 Définition par double récurrence de la suite de
Fibonacci

(i) U1 = U2 = 1
(ii) Pour n entier naturel (n > 2)
Un = Un-1 + Un-2

M Abid 8
Qu’est-ce qu’un algorithme récursif
 Un algorithme est dit récursif s’il s'appelle lui-
même
 de façon directe (récursivité directe ou
simple)
 de façon indirecte (récursivité indirecte ou
croisée)

M Abid 9
Récursivité directe
 L’algorithme comporte, dans son corps, au moins
un appel à lui-même.

...
void exemplerecursifsimple()
{
...
exemplerecursifsimple() ;
...
}
...
M Abid 10
Récursivité indirecte
 L'appel récursif d'un sous-programme R se fait dans
le corps d'un ou de plusieurs sous-programmes
appelés par R
...
void R()
{
...
P() ;
...
}
void P()
{
...
R() ; /* appel récursif de R */
...
}
...
M Abid 11
Comment réaliser un algorithme récursif ?
 De manière générale, un algorithme récursif doit
contenir:
 Une condition terminale c’est-à-dire un cas de
base ou cas trivial pouvant être résolu sans
récursivité

 Un ou plusieurs pas récursifs avec une

progression vers le cas de base à chaque appel
récursif

M Abid 12
Appel récursif
 Lors d’un appel récursif le sous-programme qui
traite le problème fait un appel à lui-même pour
traiter le cas le plus simple.
 Ceci revient donc à faire un appel avec des
paramètres différents qui sont considérés comme
« plus simples ».

M Abid 13
Arrêt de la suite d’appels récursifs
 Un appel récursif peut produire lui-même un autre
appel récursif etc. ce qui peut mener à une suite
infinie d’appels.
 Il est donc très important d‘arrêter la suite
d’appel au moment où le sous-problème peut être
résolu directement

M Abid 14
Choix du cas trivial
 Le choix de la condition d’arrêt est très
important.
 Il faut s’assurer que la condition d’arrêt est
atteinte après un nombre fini d’appels.
 Elle doit correspondre au cas le plus simple qu’on
veut traiter (cas trivial)
 Pour la factorielle, le cas le plus simple est n=0
car 0 !=1 et il respecte la décomposition
1! = 0! x 1

M Abid 15
Cas de la fonction factorielle
 La condition terminale : elle est donnée par le
cas de base 0!=1 (si on atteint 0 il suffit de
retourner 1)
 Les pas récursifs avec progression vers le cas
de base à chaque appel : si fact est le nom de
notre fonction et N un entier naturel argument
de la fonction :
➢ fact(N) retourne (N x fact(N-1))
➢ fact(N-1) retourne (N-1 x fact(N-2))
➢ etc,
➢ fact(1) retourne (1 x fact(0))
M Abid 16
Exemple
 Fonction fact équivalente à la définition
mathématique de la factorielle :
int fact(int n)
{
if (n == 0) return 1; /* Condition terminale */
return n*fact(n-1); /* Appel récursif */
}

M Abid 17
Exemple
 En vérifiant le signe de n cela donne:
int fact(int n)
{
if (n<0) {
perror(« la factorielle ne s’applique qu’aux entiers naturels »);
exit(EXIT_FAILURE); /* sortie de la fonction avec un code erreur*/
}
if (n == 0) return 1; /* Condition terminale */
return n*fact(n-1); /* Appel récursif */
}

M Abid 18
Exécution d’un algorithme récursif

 Le principe d'exécution consiste à mettre de côté

le calcul en cours tant qu'il ne sait pas le faire
 Puis reprendre les calculs en cours une fois le
résultat connu
 Le programme interrompu est mis de côté au
niveau de la pile d'exécution

M Abid 19
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -

M Abid 20
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0

5*fact(4)

M Abid 21
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4)

4*fact(3)

5*fact(4)

M Abid 22
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive

4*fact(3)

5*fact(4)

M Abid 23
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0

4*fact(3)
5*fact(4)

M Abid 24
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 25
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 26
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 27
Schéma détaillé d’exécution de l’appel fact(5)
fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 28
Schéma détaillé d’exécution de l’appel fact(5)
fact(5) - schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 29
Schéma détaillé d’exécution de l’appel fact(5)
fact(5) - schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 30
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 31
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 32
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
(cond term)

3*fact(2)
4*fact(3)
5*fact(4)

M Abid 33
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
(cond term)

1
3*fact(2)
4*fact(3)
5*fact(4)

M Abid 34
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
(cond term)

1
3*fact(2)
4*fact(3)
5*fact(4)
remontée
M Abid 35
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)

1
3*fact(2)
4*fact(3)
5*fact(4)
remontée
M Abid 36
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)

1
3*fact(2) 1
4*fact(3)
5*fact(4)
remontée
M Abid 37
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
5*fact(4)
remontée
M Abid 38
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
2
5*fact(4)
remontée
M Abid 39
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
2
5*fact(4)
remontée
M Abid 40
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
2
5*fact(4)
6
remontée
M Abid 41
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
2
5*fact(4)
6
remontée
M Abid 42
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
2
5*fact(4)
6
remontée
24
M Abid 43
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
2
5*fact(4)
6
remontée
24
M Abid 44
fact(5) Schéma détaillé d’exécution de l’appel fact(5)
- schéma 1 -
N0 fact(4) Descente récursive
N0 fact(3)
N0 fact(2)
N0
fact(1)
N0 fact(0)
N=0
1*fact(0) (cond term)
2*fact(1) 1
3*fact(2) 1
4*fact(3)
2
5*fact(4)
6
remontée
24
120
M Abid 45
Notion de pile d’exécution
 La pile d'exécution d'un programme en cours est
un emplacement mémoire destiné à mémoriser les
paramètres, les variables locales ainsi que les
adresses de retour des fonctions en cours
d'exécution
 La pile d'exécution fonctionne selon le principe
LIFO (Last In First Out): dernier entré premier
sorti
 Attention ! la pile a une taille fixée, une mauvaise
utilisation de la récursivité peut entraîner un
débordement de pile (stack overflow).

M Abid 46
Pile d’exécution et récursivité
 De façon générale, à chaque appel de fonction, le
système empile l’environnement de la fonction au
niveau de la pile d’exécution. La grande
différence entre une fonction effectuant un
traitement itérativement et une fonction
effectuant le même traitement récursivement est
que :
 La fonction itérative est appelée une seule fois :
un seul environnement est empilé
 La fonction récursive est appelée 𝑝 fois : 𝑝
environnements sont empilés.

M Abid 47
États de la pile à l’exécution de fact(4)

N=4

Appel fact
en
cours (4)
États de la pile à l’exécution de fact(4)

N=4

Appel fact
en
cours (4)
États de la pile à l’exécution de fact(4)

N=4

Appel fact
en
cours (4)
fact
États de la pile à l’exécution de fact(4)

N=4

Appel fact
en
cours (4)
fact ?
États de la pile à l’exécution de fact(4)
Niveau
de réc

0 N=4

Appel fact
en
cours (4)
fact ?
États de la pile à l’exécution de fact(4)
Niveau
de réc

N=3

0 N=4 N=4

Appel fact fact

en
cours (4) (3)
fact ? ?
États de la pile à l’exécution de fact(4)
Niveau
de réc

1 N=3

0 N=4 N=4

Appel fact fact

en
cours (4) (3)
fact ? ?
États de la pile à l’exécution de fact(4)
Niveau
de réc

1 N=3

0 N=4 N=4

M Abid 79
Exemple de récursivité non terminale
 Dans les exemples précédents, factorielle est non
terminale :
 Bien que le cas d'arrêt renvoie une constante, celui de
l'appel récursif modifie la valeur renvoyée en la
multipliant par n avant de lui-même renvoyer une valeur

M Abid 80
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de
récursivité
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel
récursivité exécuté
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à

récursivité exécuté calculer
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 )
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 )
Schéma détaillé d’exécution de l’appel fact(5)

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 )

2 fact( 3 ) 3 * fact( 2 )

3 fact( 2 )
Schéma détaillé d’exécution de l’appel fact(5)

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 )

2 fact( 3 ) 3 * fact( 2 )

3 fact( 2 ) 2 * fact( 1 )

4 fact( 1 ) 1 * fact( 0 )

Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 )

remontée
2 fact( 3 ) 3 * fact( 2 )

3 fact( 2 ) 2 * fact( 1 ) 2*1=2

4 fact( 1 ) 1 * fact( 0 ) 1*1=1

5 fact( 0 ) point terminal/d'appui/d'arrêt 1

Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 )

remontée
2 fact( 3 ) 3 * fact( 2 )

3 fact( 2 ) 2 * fact( 1 ) 2*1=2

4 fact( 1 ) 1 * fact( 0 ) 1*1=1

5 fact( 0 ) point terminal/d'appui/d'arrêt 1

Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 )

remontée
2 fact( 3 ) 3 * fact( 2 ) 3*2=6

3 fact( 2 ) 2 * fact( 1 ) 2*1=2

4 fact( 1 ) 1 * fact( 0 ) 1*1=1

5 fact( 0 ) point terminal/d'appui/d'arrêt 1

Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 )

remontée
2 fact( 3 ) 3 * fact( 2 ) 3*2=6

3 fact( 2 ) 2 * fact( 1 ) 2*1=2

4 fact( 1 ) 1 * fact( 0 ) 1*1=1

5 fact( 0 ) point terminal/d'appui/d'arrêt 1

Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 ) 4 * 6 = 24

remontée
2 fact( 3 ) 3 * fact( 2 ) 3*2=6

3 fact( 2 ) 2 * fact( 1 ) 2*1=2

4 fact( 1 ) 1 * fact( 0 ) 1*1=1

5 fact( 0 ) point terminal/d'appui/d'arrêt 1

Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 )

Descente récursive
1 fact( 4 ) 4 * fact( 3 ) 4 * 6 = 24

remontée
2 fact( 3 ) 3 * fact( 2 ) 3*2=6

3 fact( 2 ) 2 * fact( 1 ) 2*1=2

4 fact( 1 ) 1 * fact( 0 ) 1*1=1

5 fact( 0 ) point terminal/d'appui/d'arrêt 1

Schéma détaillé d’exécution de l’appel fact(5)

Niveau de Appel Valeur à Valeur

récursivité exécuté calculer retournée

0 fact( 5 ) 5 * fact( 4 ) 5 * 24 = 120

Descente récursive
1 fact( 4 ) 4 * fact( 3 ) 4 * 6 = 24

remontée
2 fact( 3 ) 3 * fact( 2 ) 3*2=6

3 fact( 2 ) 2 * fact( 1 ) 2*1=2

4 fact( 1 ) 1 * fact( 0 ) 1*1=1

5 fact( 0 ) point terminal/d'appui/d'arrêt 1

Récursivité terminale
 Une fonction est dite récursive terminale si
l'appel récursif est de la forme return f(…)
 Autrement dit, la valeur retournée au niveau du
point d’appui est directement la valeur obtenue
par un appel récursif sans qu'il n'y ait aucune
modification sur cette valeur

M Abid 110
Exemple de récursivité terminal:
la fonction PGCD
 A et B étant deux entiers positifs, on a les
propriétés arithmétiques suivantes :

(i) PGCD(A,B) = A si A=B

(ii) PGCD(A,B) = PGCD(A-B,B) si A>B

(iii) PGCD(A,B) = PGCD(A,B-A) si A<B

M Abid 111
Fonction PGCD en C

int PGCD(int A, int B)

{
if( A == B) return A; /* condition terminale */
if (A >B) return PGCD(A-B, B); /* appel récursif*/
if (A <B) return PGCD(A, B-A); /* appel récursif*/
}

M Abid 112
exécution de la fonction PGCD(80,15)
Niveau de fonction fonction valeur
récursivité exécutée appelée retournée

0 PGCD(80,15) PGCD(65,15)

1 PGCD(65,15) PGCD(50,15)

2 PGCD(50,15) PGCD(35,15)

3 PGCD(35,15) PGCD(20,15)
4 PGCD(20,15) PGCD(5,15)
5 PGCD(5,15) PGCD(5,10)
6 PGCD(5,10) PGCD(5,5)
7 PGCD(5,5)
exécution de la fonction PGCD(80,15)
Niveau de fonction fonction valeur
récursivité exécutée appelée retournée

0 PGCD(80,15) PGCD(65,15)

1 PGCD(65,15) PGCD(50,15)

2 PGCD(50,15) PGCD(35,15)

0 PGCD(80,15) PGCD(65,15)

1 PGCD(65,15) PGCD(50,15)