La Récursivité
Licence 2 D2A et SRT
Dr Youssou KASSE
Université Alioune Diop de
Bambey
[Link]@[Link]
Définition
Un sous programme est dit récursif si son corps
contient un appel à lui-même, dit appel récursif.
Avant de se lancer dans l’écriture d’une fonction
ou d’une procédure récursive, il faut:
• Trouver le programme ou l’expression commune à
tous les appels récursifs à la fonction;
• Trouver le point d’arrêt de la récursivité
• Vérifier qu’à chaque fois que la fonction ou la
procédure s’appelle, elle se rapproche de son point
d’arrêt
Dr KASSE 2
Exemple: factoriel d’un nombre (Etape 1)
Commençons par chercher l’expression commune à
tous les appels récursifs de la fonction considérée.
Prenons un exemple en calculant la factorielle de 4
Définition 1 : n! = 1 × 2 × 3 × ... × (n - 1) × n
Définition 2 : 0! = 1 et quelque soit n > 0, n! = n ×
(n - 1)!
L’expression commune à chaque étape est: la
factorielle d’une valeur « n » est « n » fois la
factorielle de « n-1 ».
Dr KASSE 3
Exemple: factoriel d’un nombre
Etape 2: trouver le point d’arrêt de la récursivité
On connaît la valeur de 1! Qui vaut 1. Donc 1! est
notre point d’arrêt.
Etape 3: vérifier qu’à chaque appel, la fonction se
rapproche du point d’arrêt.
Le point de départ de notre calcul est une valeur
‘’n’’ strictement positive.
A chaque étape, on diminue ‘’n’’ de 1 donc on
finira bien par atteindre la valeur n=1
Dr KASSE 4
Algorithme de la fonction factoriel
int fact( int n)
{
int res;
if (n==1)
res=1;
else
{
res= n*fact(n-1);
}
return (res);
}
Le programme spécifie en effet que si le paramètre est 1, alors le
résultat est 1. Sinon, le résultat vaut n fois le factoriel de n-1.
Dr KASSE 5
Application: Calcul de la factorielle de 4
Retourne Si n=1 alors Nouvel appel à la fonction Factorielle pour calculer 3!
24 à Sinon Dans cette nouvelle instance de la fonction, n vaut 3
l’appelant retourner 4*?
Si n=1 alors
Retourne 6 à Sinon
l’appelant. Ce qui retourner 3*? Nouvel appel à la fonction Factorielle pour
permet de calculer 4! calculer 2! n vaut 2
Si n=1 alors
Retourne 2 à l’appelant. Ce qui Sinon
permet de calculer 3! retourner 2*?
Nouvel appel à la fonction
Factorielle pour calculer 1!
Valeur d’arrêt
Retourne 1 à l’appelant. Ce qui
permet de calculer 2! Si n=1 alors
retourner 1
Dr KASSE 6
Application: suite de Fibonacci
Quand le corps d'une fonction comporte plusieurs appels
récursifs, les différents appels peuvent être représentés sous la
forme d'un arbre. L'exemple classique est celui de la
définition récursive de la suite de Fibonacci :
int fib ( int n)
{
if (n <= 1)
return 1;
else
return fib(n-1) + fib(n-2);
}
Dr KASSE 7
Arbre des appels de fib(4)
Arbre des appels de la suite de Fibonacci
Arbre des appels de la suite de Fibonacci
Dr KASSE 8
Avantages et inconvénients de la
récursivité
La récursivité permet d’écrire des algorithmes
concis et élégants.
Elle permet de transcrire de façon quasi littérale
certaines définitions mathématiques, souvent
appelées récurrences.
Cependant, il y a le risque d’une grande
occupation de la mémoire.
Les temps d’exécution peuvent aussi être longs.
Dr KASSE 9
Récursivité simple ( un seul appel récursif)
Considérons la fonction puissance x xn. Cette fonction
peut être définie récursivement :
L’algorithme correspondant s’écrit :
double puissance (double x, int n)
{
if (n==0)
return 1;
else
return x*puissance (x, n-1);
}
Dr KASSE 10
Récursivité multiple (plus d’un appel
récursif)
Nous voulons calculer les combinaisons en se servant de
la relation de Pascal :
L’algorithme correspondant s’écrit :
int combinaison (int n, int p)
{
if(( p==0) or (p==n))
return 1
else
return combinaison (n-1, p) + combinaison (n-1, p-1)
}
Dr KASSE 11
Récursivité mutuelle
Des définitions sont dites mutuellement récursives si elles
dépendent les unes des autres. Ça peut être le cas pour la
définition de la parité :
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
FinFonction FinFonction
Dr KASSE 12
Récursivité imbriquée: La fonction
d’Ackermann
La fonction d’Ackermann est définie comme suit :
Fonction ACKERMANN(m : entier, n : entier): entier
Début
si (m = 0) alors
retourner n+1
sinon si (n = 0) alors
retourner ACKERMANN(m - 1, 1)
sinon
retourner ACKERMANN(m - 1, ACKERMANN(m, n - 1))
FinSi
FinFonction
Dr KASSE 13
Le paradigme diviser pour régner
C’est une méthode de décomposition/recomposition, qui
permet d'écrire assez facilement des algorithmes parmi les
plus intéressants, voire les plus efficaces.
PRINCIPE:
Diviser : le problème en un certain nombre de sous-
problèmes ;
Régner : sur les sous-problèmes en les résolvant
récursivement ou, si la taille d’un sous-problème est assez
réduite, le résoudre directement ;
Combiner : les solutions des sous-problèmes en une
solution complète du problème initial.
Dr KASSE 14
Exemple : la dichotomie
Pour rechercher une valeur particulière v dans un tableau
d’entiers ordonné dans l’ordre croissant, on peut procéder
par dichotomie, c'est-à-dire que l'on procède par divisions
successives du tableau en deux parties.
Soient v la valeur à rechercher, deb et fin les indices de
début et de fin du tableau tab. Soit m l’indice de milieu du
tableau.
Si v = tab[m] alors la valeur recherchée est au milieu du
tableau. Sinon si v < tab[m] alors la valeur recherchée est
dans l'intervalle [deb, m-1]. Sinon elle est dans l'intervalle
[m+1, fin].
Dr KASSE 15
Application: Recherche par dichotomie
Fonction estPresent(tab : tableau[MAX] d'entier, v : entier, deb: entier, fin : entier) : booléen
variable
m : entier
Début
si (deb > fin) alors
retourner FAUX
FinSi
m = (deb+fin) div 2
si (tab[m] = = v) alors
retourner VRAI
sinon si (tab[m] > v) alors
retourner estPresent(tab,v,deb,m-1)
sinon
retourner estPresent(tab,v,m+1,fin)
FinSi
FinFonction
Dr KASSE 16
FIN
Dr KASSE 17
