Algorithmique

Pr. RAOUYANE Brahim

Département Mathématiques & Informatique
SMI3 2014

1
 Résumé
Fonction Nom_Fonction(var:type,var:type):type Procédure Nom_Procédure(var:type,var:type)
Variables internes Variables internes
DébutFonction DébutProcédure
Instructions Instructions
……….. ………..
Retourner variable; Instructions
FinFonction FinProcédure

Algorithme principale
Variables : ………(Globales)
Constantes: ………..
Fonctions: …………
Début
variable ←Nom_Fonction(var,var)
Nom_Fonction(var,var) Appel d’une Fonction
Ecrire(Nom_Fonction(var,var))
Nom_Procédure(var,var) Appel d’une Procédure
…………
Fin
2
Récursivité

3
Plan
I. Définition et exemples
II. Types de récursivité
III. Algorithme récursif
IV. Exemple : Les tours de Hanoï
V. Recette de la récursivité
VI. Exécution des algorithmes
récursifs
[Link] et tris récursifs
4
Définition et exemples

5
 Qu'est-ce que la récursion ?
 Définition linguistique:
 Le mot « récursion » vient du latin recursare
qui signifie courir en arrière, revenir.
 L'idée de réapparition, de retour, est donc
étymologiquement liée à la récursivité.
 Définition:
 Lorsqu'un système contient une autoréférence
(ou une copie de lui-même), on dit que ce
système est récursif.

6
 Exemples
 Dans le domaine végétal, le romanesco (hybride broccolo/choux-fleur) est très
récursif.

 L'effet droste (image en abyme).

7
 Exemples
 Les poupées russes ou matriochkas sont des séries de
poupées de tailles décroissantes placées les unes à
l'intérieur des autres. Une poupée russe est donc :
 Soit une poupée « pleine » (qu'on ne peut ouvrir),
 Soit une poupée « vide » contenant une poupée russe.

8
 Conclusion
 La récursivité est un concept très puissant quand on
sait décomposer un problème en un ou
plusieurs sous-problèmes qui sont de même
nature, mais qui s'appliquent à un nombre d'objets
plus réduit.
 De même quand on sait décomposer un objet en
groupes de composants qui présentent les mêmes
propriétés que l'objet lui-même et qui ne contiennent
qu'un sous-ensemble de l'objet.

9
Types de Récursivité

10
 Définition
 Une définition récursive est une définition dans laquelle intervient ce
que l'on veut définir.
 Un algorithme récursif est un algorithme défini en fonction de lui-
même.
 Une procédure (ou fonction) P est dite récursive si son
exécution peut provoquer un ou plusieurs appels (dits récursif) à P.
 Récursivité Simple
 Récursivité Multiple
 Récursivité Mutuelle
 Récursivité Imbriquée
 Récursivité Terminale

11
 Récursivité simple
 Définition
 Une récursivité simple contient un seul appel récursif à P
dans le corps d'une procédure récursive P.
 Exemple
 Un escalier de hauteur c'est :
 Vision Itérative: une séquence de marches
 Vision Récursive: une marche suivie d'un escalier de hauteur

12
 Récursivité simple

 Vision Récursive: une marche suivie d'un escalier de

hauteur
 L'algorithme Récursif correspondant s'écrit :
Action monterEscalier ( h : Entier )
Début
Si ( h > 0 ) Alors
monterMarche ( )
monterEscalier ( h - 1 )
FinSi
Fin
13
 Récursivité multiple
 Définition
 Une récursivité est multiple si il y a plusieurs appels
récursifs à P dans le corps d'une procédure récursive P.
 Exemple
 La suite de Fibonacci est définie par ( entier naturel) :

14
 Récursivité multiple
 La suite de Fibonacci est définie par ( entier naturel) :

 L'algorithme correspondant s'écrit :

Fonction fib( n : Entier ) : Entier
Début
Si ( n = 0 Ou n = 1 ) Alors
Retourner ( n )
Sinon
Retourner ( fib ( n - 1 ) + fib ( n - 2 ) )
FinSi 1 2
Fin
15
 Récursivité mutuelle
 Définition
 Une récursivité est mutuelle ou croisée quand une procédure
P appelle une procédure Q qui déclenche un appel
récursif à P.
 Remarque
 La situation est obligatoirement symétrique, puisque Q déclenchera un
appel de P, qui déclenchera à son tour un appel de Q.
 Exemple
 La parité d'un entier naturel peut être définie par :

16
 Récursivité mutuelle
 Les algorithmes correspondants s'écrivent :
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
Retourner ( impair ( n - 1 ) ) Retourner ( pair ( n - 1 ) )
FinSi FinSi
Fin Fin

 Les fonctions pair() et impair() s'invoquent mutuellement :

 pair(3) -> impair(2) -> pair(1) -> impair(0)
 La dernière invocation renvoie Faux :
 impair(0)=Faux -> pair(1)=Faux -> impair(2)=Faux -> pair(3)=Faux -> Faux

17
 Récursivité imbriquée
 Définition
 Une récursivité est imbriquée si une procédure récursive P
contient un appel imbriqué.
 Exemple
 La fonction d'Ackermann ( et entiers naturels) est définie
comme suit :

18
 Récursivité imbriquée
 L'algorithme de la fonction d'Ackermann correspondant
s'écrit :
Fonction ackermann ( n , p : Entier ) : Entier
Début
Si ( n = 0 ) Alors
Retourner ( p + 1 )
Sinon
Si ( p = 0 ) Alors
Retourner ( ackermann ( n - 1 , 1 ) )
Sinon
Retourner ( ackermann ( n - 1 , ackermann ( n , p - 1 ) )
FinSi
FinSi
Fin
19
 Récursivité terminale
 Définition
 La récursivité est terminale si l'appel récursif est la dernière
instruction et elle est isolée.
 Exemple
 L'addition de deux entiers positifs ou nuls peut être définie
comme suit :
Fonction plus ( a , b : Entier ) : Entier
Début
Si ( b = 0 ) Alors
Retourner ( a )
Sinon
Retourner ( plus ( a + 1 , b - 1 ) )
FinSi
Fin

 plus(4,2)=plus(5,1)=plus(6,0)=6
20
 Récursivité terminale
 Définition
 La récursivité n'est pas terminale si l'appel récursif n'est pas
la dernière instruction et/ou elle n'est pas isolée (elle fait
partie d'une expression).
 Exemple : Retour sur l'addition :
Fonction plus ( a , b : Entier ) : Entier
Début
Si ( b = 0 )
Retourner ( a )
Sinon
Retourner ( 1 + plus ( a , b - 1 ) )
FinSi
Fin
 plus(4,2)=1+plus(4,1)=1+1+plus(4,0)=1+1+4=6
21
 Exercice
 Ecrire un Procédure qui permet d’afficher les entiers par
ordre croissant
 Ecrire un Procédure qui permet d’afficher entiers par ordre
croissant puis décroissant

22
 Exercice
 Ecrire un Procédure qui permet d’afficher les entiers par
ordre croissant
 Définition
Procédure Croissant ( n : Entier )
Début
Si ( n > 0 ) Alors
Croissant ( n - 1 )
Ecrire( n )
FinSi
FinProcédure

23
 Exercice: Ordre de l’appel
 La procédure elle se simplifie en :

Procédure Croissant ( n : Entier )

Début
Si ( n > 0 ) Alors
Ecrire( n )
Croissant ( n - 1 )
Ecrire( n )
FinSi
FinProcédure
24
Algorithme récursif

25
 Récursivité
 Définition
 Un algorithme est dit récursif si l'expression qui le définit fait appel à lui-
même. On qualifiera de récursif, un appel à une fonction f provoqué par
l'évaluation d'un autre appel à f.
 Critères pour un bon algorithme récursif
 Règle 1 : Un algorithme récursif doit être défini par une expression
conditionnelle dont l'un au moins des cas mène à une expression
évaluable sans appel récursif.
 Une telle expression est appelée condition d'arrêt ou test
d'arrêt ou clause terminale ou cas de base ou encore cas
trivial.
 Règle 2 : Il faut s'assurer que pour toute valeur du (ou des)
paramètre(s), il suffira d'un nombre fini d'appels récursifs pour
atteindre la condition d'arrêt.

26
 Récursivité
 Schéma général d'un algorithme récursif
Action R(données X ; résultats Y)
Début
si terminaison(X) alors
Y ...
sinon
...
R(entrée_réduite, ...)
...
Finsi
Fin
27
 Récursivité multiple
 Schéma général d'une fonction récursive
Fonction F (a1 : T1 ; a2 : T2...) : T
var rs : T
Début
Si terminaison(a1, a2,...) alors
rs ...
Sinon
y1 ...
y2 ...
...
rs f(y1, y2, ...)
...
Finsi
Retourner(rs)
Fin
28
 Exercice
 Affiche un entier sous la forme d’une suite de
ses chiffres de la droite vers la gauche puis de
la gauche vers la droite.
 Exemple d'exécution.
Votre entier? 12354
==> De droite à gauche
45321
==> De gauche à droite
12354
29
 Exercice( Correction )
Procédure AfficherChiffreDG ( n : Entier )
Début
Si ( n > 0 ) Alors
Afficher ( Modulo ( n , 10 ) )
AfficherChiffreDG ( DivEnt ( n , 10 ) )
FinSi
Fin Procédure
Procédure AfficherChiffreGD ( n : Entier )
Début
Si ( n > 0 ) Alors
AfficherChiffreGD ( DivEnt ( n , 10 ) )
Afficher ( Modulo ( n , 10 ) )
FinSi
Fin Procédure
30
 Exercice(Correction)
Algorithme pg_rcchiffresA
Variable n : Entier
Début
Afficher ( "Votre entier? " )
Saisir ( n )
Afficher ( "==> De droite à gauche " )
AfficherChiffreDG ( n )
Afficher ( "==> De gauche à droite " )
AfficherChiffreGD ( n )
Fin Action
31
Les tours de Hanoï

32
 Problème
 Les tours de Hanoï est un jeu solitaire dont l'objectif est de déplacer
les disques qui se trouvent sur une tour (par exemple ici la première
tour, celle la plus à gauche) vers une autre tour (par exemple la
dernière, celle la plus à droite) en suivant les règles suivantes :
 On ne peut déplacer que le disque se trouvant au sommet d'une tour
 On ne peut déplacer qu'un seul disque À la fois
 Il est interdit de poser un disque sur un disque plus petit

33
 Les tours de Hanoï
Problème

Problème :
Soit n tours de tailles décroissantes sur un socle A,
transférer les n tours sur le socle B en utilisant un socle
intermédiaire C.

Déplacement d’une tour : on ne peut empiler

qu’une tour de plus petite taille sur une autre tour

Tige A Tige B Tige C

 Résolution
 Hypothèse
 On suppose que l'on sait résoudre le problème pour n disques.
 Principe
 Pour déplacer n disques de la tige A vers la tige C :
1) on déplace n-1 les plus petits de la tige A vers la tige B,
2) on déplace le plus gros disque de la tige A vers la tige C,
3) on déplace les n-1 plus petits de la tige B vers la tige C.
 Validité
 Les règles sont respectées puisque le plus gros disque est
toujours en « bas » d'une tige et que l'hypothèse (de
récurrence) nous assure que nous pouvons déplacer la « pile »
de disques en respectant les règle.

35
 Résolution

Socle A Socle B Socle C

Socle A Socle B Socle C

 Algorithme
 L'algorithme suivant déplace n disques de la tour orig(ine)
vers la tour dest(ination) en passant par la tour
inter(médiaire).
Procédure hanoi ( n : Entier ; orig , dest , inter : Chaîne )
Début
Si ( n > 0 ) Alors
hanoi ( n - 1 , orig , inter , dest )
deplacer ( orig , dest )
hanoi ( n - 1 , inter , dest , orig )
FinSi
Fin

37
 Arbre des appels (n=3)
1
Hanoi (3,A,B,C)

2 8 9

Hanoi (2,A,C,B) Déplacer (A,B) Hanoi (2,C,B,A)

3 10
5 6
Déplacer (C,A)
Hanoi (1,A,B,C) Déplacer (A,C) Hanoi (1,B,C,A)
11
4 7 Déplacer (C,B)
Déplacer (A,B) Déplacer (B,C) 12
Déplacer (A,B)
 Arbre des appels (n=3)
1) Déplacer le disque 1 de la tour 1 à la tour 3.
2) Déplacer le disque 2 de la tour 1 à la tour 2.
3) Déplacer le disque 1 de la tour 3 à la tour 2.
4) Déplacer le disque 3 de la tour 1 à la tour 3.
5) Déplacer le disque 1 de la tour 2 à la tour 1.
6) Déplacer le disque 2 de la tour 2 à la tour 3.
7) Déplacer le disque 1 de la tour 1 à la tour 3.
 Exécution avec trois disques
 Résultat d'exécution (Avec trois disques)
 Nombre de disques? 3
1  deplacer de A sur C
2  deplacer de A sur B
3  deplacer de C sur B
4  deplacer de A sur C
5  deplacer de B sur A
6  deplacer de B sur C
7  deplacer de A sur C
40