RECURSIVITE

Généralités
Récursivité = technique puissante pour des définitions
mathématiques
Définir un ensemble infini d’objets au moyen d’une phrase
finie:
- 0 est un entier naturel
- le successeur d’un entier naturel est un entier naturel
Pourquoi étudier la récursivité?
1. Moyen simple
2. Preuve de correction
3. Mécanisme de base pour de nombreux langages
Quand Utilise_t_on la récursivité?
1. Problème P se décomposant en 2 ou plusieurs sous
problèmes de même nature que P mais de complexité
moindre
2. Objet / structure récursive

Quand ne pas utiliser la récursivité?

1. Définition itérative évidente
2. Programme du type:
P ≡ si B alors S ; P fsi
ou  P ≡ tant que B faire S fait
P ≡ S ; si B alors P fsi

Principes de l’analyse :
- Formule de récurrence
- Critère d’arrêt
Exemple:
Un exemple de tous les jours: factoriel!
n! = n × (n − 1) × · · · × 2 × 1 .
fact( n ) = si n = 0 alors 1
sinon n * fact( n-1 ) fsi
Exécution :
Calcul de 4! :
fact(4) ⇒ 4*fact(3) ⇒ 4*3*fact(2) ⇒ 4*3*2*fact(1) ⇒
4*3*2*1*fact(0) ⇒ 4*3*2*1*1= 24

Le principe de l’exécution

Le principe de l’exécution est simple : l’algorithme met de côté (dans une

PILE) ce qu’il ne sait pas faire quitte à les reprendre après!

Le principe de la programmation

On doit dire à l’algorithme comment faire dans les cas les plus
simples ⇒ L E S C O N D I T I O N S D’A R R Ê T ! Dans les cas complexes, l’algorithme
va faire appel à lui-même en S I M P L I F I A N T ces cas jusqu’à tomber sur l’une des
conditions d’arrêt.
Résolution d’un problème P fondée sur :
- résolution de P dans certains cas particuliers
- décomposition de P en sous problèmes de même nature que P
- déduction du résultat de P à partir des résultats intermédiaires par une
règle de calcul.

Exemples de programmes FAUX!

Si ces principes ne sont pas appliqués, l’algorithme
risque soit de ne pas produire de résultat, soit de
tourner à l’infini.

Pas de conditions d’arrêt ⇒ CALCUL INFINI

fact( n ) = n * fact( n-1 )

Pas de simplification du cas à traiter

fact( n ) = si n = 0 alors 1
sinon n * fact( n+1 ) fsi // on ne dirige pas la fonction vers
la condition d’arrêt.
Technique : Moyen simple et élégant Comment ça marche ?
pour résoudre certains problèmes. Appel à fact(4)
. 4*fact(3) = ?
. Appel à fact(3)
Définition:
. . 3*fact(2) = ?
Une construction est récursive si elle se . . Appel à fact(2)
définit à partir d'elle-même.
. . . 2*fact(1) = ?
On appelle récursive toute fonction ou . . . Appel à fact(1)
procédure qui s’appelle elle même. . . . . 1*fact(0) = ?
. . . . Appel à fact(0)
Exemple: factoriel! . . . . Retour de la valeur 1
. . . . 1*1
n! = n × (n − 1) × · · · × 2 × 1 . . . . Retour de la valeur 1
fact( n : entier ) : entier . . . 2*1
Debut . . Retour de la valeur 2
si n = 0 alors fact := 1 . . 3*2
sinon fact := n * fact( n-1 ) . Retour de la valeur 6
fsi . 4*6 Retour de la valeur 24
Fin
Algorithmes récursifs : les règles de conception

Première règle:
Tout algorithme récursif doit distinguer plusieurs cas, dont
l’un au moins ne doit pas comporter d’appel récursif. Souvent
ce sont les cas les plus simples.
Sans cela, on risque de tourner en rond et de faire des
exécutions qui ne se finissent pas.

Conditions d’arrêt.
Ces cas non récursifs sont appelés cas de base et les
Conditions que doivent satisfaire les données dans ces cas de
base sont appelées conditions d’arrêt ou de terminaison .
Seconde règle:
On doit conduire le programme vers les cas de base :
tout appel récursif doit se faire avec des données plus
Proches des conditions de terminaison!
Cette règle utilise le théorème suivant :
Théorème:
Il n’existe pas de suite infinie strictement décroissante
d’entiers positifs ou nuls.

Ainsi, l’arrêt de l’exécution d’un programme récursif est

garanti quand les deux règles sont appliquées!
Les différents types de récursivité:
Plusieurs types :
1. récursivité terminale, la fonction se termine
avec l’unique appel récursif.
2. récursivité multiple , si l’un des cas traité se
résout avec plusieurs appels récursifs.
3. récursivité croisée ou mutuelle , deux
algorithmes sont mutuellement récursifs si
l’un fait appel à l’autre et vice-versa.
4. récursivité imbriquée, si la fonction contient
comme paramètre un appel à elle-même
Notation:
f(x1 , x2 ,……, xn ) = EXP
f : fonction à définir
x1 , x2 ,……, xn : les paramètres de f
EXP : expression comportant:
*conditionnelles
*expressions à résultat booléen
*expressions utilisant des appels de
fonctions ou d’opérateurs
Exemple :
f(X) = Si X = 0 ou X = 1 alors 1
sinon f(X-1) + f(X-2) fsi
Exemples:

1. Soit à calculer p(x , y) = xy

- cas particulier : y = 0  x0 = 1
xy/2 * xy/2 si y pair
- formule de récurrence : xy =
xy/2 * xy/2 * x si y impair

p(x , y ; z) : si y = 0 alors z := 1
sinon p(x , y/2 ; u)
si pair(y)
alors z := u * u
sinon z := u * u * x
fsi
fsi
 Problème 1
Problème : écrire une fonction récursive qui
inverse l'ordre des éléments dans un tableau
d'entiers.
3 5 7 2 0

0 2 7 5 3
 Problème 1
Problème : écrire une fonction récursive qui inverse
l'ordre des éléments dans un tableau d'entiers.
1- Décomposition du traitement : on échange les
éléments situés aux extrémités du tableau, et on
inverse l'ordre des éléments situés entre ces deux
extrémités.
3 5 7 2 0

2- Condition d'arrêt : l'inversion doit s'arrêter quand

la partie à inverser contient un seul élément ou
est vide
 Problème 1
Inverse_tab( var T : tab_entier ; deb,fin : entier)
Debut
Si deb < fin
alors u := T[deb]
T[deb] := T[fin]
T[fin] := u
inverse_tab(T,deb+1,fin-1)
fsi
Fin
Appel initial : inverse_tab(T,1,N)
 Problème 2
Problème : calculer la somme des éléments d’un
tableau de taille N
3 5 7 2 10

Résultat : 27
 Problème 2
Problème : calculer la somme des éléments d’un
tableau de taille N
1- Décomposition du traitement : on calcule la
somme de N-1 éléments et on lui ajoute le
dernier élément

3 5 7 2 10

2- Condition d'arrêt : la somme des éléments

d’un tableau vide = 0
 Problème 2
Somme( T : tab_entier ; N : entier) : entier
Debut
Si N=0 alors Somme := 0
sinon Somme := Somme(T,N-1) + T[N]
fsi
Fin
Appel initial : Somme(T,N)
 Problème 2
Somme( T : tab_entier ; deb,fin : entier) : entier
Debut
Si deb > fin alors Somme := 0
sinon Somme := Somme(T,deb+1,fin) + T[deb]
fsi
Fin
Appel initial : Somme(T,1,N)
 Problème 3
Problème : Tester si un mot est un palindrome
Un mot est un palindrome ssi il peut être lu de
gauche à droite ou de droite à gauche
gag ; kayak ; php ; radar ; ……
 Problème 3
K A Y O K

K A Y A K

1- Décomposition du traitement : on compare

les caractères situés aux extrémités du mot:
- si égalité on teste le reste du mot
- si différence on s’arrête
2- Condition d'arrêt : un mot vide ou un mot
contenant un seul caractère est un palindrome
 Problème 3
Palindrome( M : chaîne ; deb,fin : entier) : booléen
Debut
Si deb ≥ fin
alors Palindrome := vrai
sinon si M.str[deb] = M.str[fin]
alors Palindrome := Palindrome(M,deb+1,fin-1)
sinon Palindrome := faux
fsi
fsi
Fin
Appel initial : Palindrome (M,1,M.taille)
 Problème 4
Étant donné un polynôme P = a0 +a1 X +: : :+an Xn à
coefficients réels et un nombre réel X, on veut calculer la
valeur P(x).
La méthode naïve consiste à calculer séparément les
puissances de X : 1, X, ..., Xn puis à les
multiplier par les ai correspondants, et à additionner le tout.
Le schéma de Horner consiste au contraire à calculer P(x) en
utilisant l'égalité suivante :
an Xn + an-1 Xn-1 + …… + a0 = (((an X + an-1 )X + an-2 )X ….)X + a0

En représentant le polynôme P par un tableau de taille n+1

contenant ses coefficients, écrire une fonction qui calcule P(x)
en utilisant le schéma de Horner.
 Problème 4
On représente le polynôme comme suit :
an an-1 . . . . . . a1 a0

tab_réel = tableau[1..Max] de réel

Horner(T : tab_réel, deb, fin : entier; X:réel): réel
Si deb ≤ fin
alors Horner := T[fin] + Horner(T, deb, fin-1) * X
fsi
 Problème 5 : Tours de Hanoï
Trois tours représentées par des tiges sont
disposées les unes à côté des autres.
N disques de tailles différentes, classés par ordre
croissant de taille sont déposés sur la première
tour, tel que, le plus large est en bas, le moins
large en haut.
L'objectif est de faire passer tous les disques sur la troisième
tour, en utilisant la deuxième comme tour intermédiaire.
Sur cette troisième tour, les disques seront classés de la même
manière qu'ils l'étaient sur la première.

Les règles sont les suivantes :

*il est interdit de poser un disque sur un autre de taille inférieure.

*on ne peut déplacer qu'un seul disque à la fois.
 Problème 5
Hanoi(dep,arr,n : entier) :
Si n>0 alors Hanoi(dep,intermédiaire(dep,arr),n-1)
Déplacer(n,dep,arr)
Hanoi(intermédiaire (dep,arr),arr,n-1)
Fsi
Les tours sont numérotées 1, 2, 3
intermédiaire (a,b :entier) : entier
Debut
intermédiaire := 6-a-b
Fin
Déplacer(n,dep,arr) : déplacer le disque numéro n depuis
la tour dep vers la tour arr.