Ecole Supérieure de Technologie et d’Informatique
Année universitaire : 2011-2012
Module : Programmation 2
TD N°2
La récursivité
Mme BELKADHI CHELBI H.
1. Introduction à la récursivité
Un sous-programme est dit récursif lorsqu’il fait appel à lui-même ou à des sous-programmes qui
lui font référence. La programmation récursive est une technique de programmation qui remplace
les instructions de boucle (while, for, etc.) par des appels de fonction.
On parle de récursivité directe lorsque le sous-programme s’appelle lui-même et de récursivité
croisée lorsque plusieurs sous-programmes s’appellent mutuellement.
1.1. Exemple classique de calcul de factorielle
Considérons l’exemple de la factorielle. A un entier naturel n donné on associe l’entier, noté n!,
défini par :n! = n × (n − 1).(n − 2) × ... × 2 × 1, et en particulier 0! = 1.
….
Avec un programme itératif
Nous savons programmer cette fonction sans faire appel à la récursivité. En général, il intervient
alors au moins une boucle, ou itération. On parle alors de programme itératif, par opposition à un
programme récursif, dans lequel intervient de la récursivité.
On a donc le programme suivant :
#include <stdio.h>
int fact(int n)
{
int F, k;
F = 1;
Advertisement
for (k = 2; k <= n; k++) F = F*k;
return F;
}
void main( )
{
int n;
printf("n = ");
scanf("%d",&n);
printf("%d! = %d.\n", n, fact(n));
}
Avec un programme récursif
Le programme récursif repose sur la définition récursive suivante de la fonction factorielle :
0! = 1,(n + 1)! = (n + 1) × n!.
Ceci donne lieu au programme suivant :
#include <stdio.h>
int fact(int n)
{
if (n == 0) return 1;
else return n*fact(n-1) ;
}
void main( )
{
int n;
printf("n = ");
scanf("%d",&n);
printf("%d ! = %d.\n", n, fact(n));
}
Advertisement
1.2. Pour résumer
Nous allons généraliser le cas précédent sur la factorielle.
Une fonction récursive doit TOUJOURS être composée des éléments suivants :
- Un ou plusieurs "cas d'arrêt(s)". Ce sont des tests (souvent if( )) vérifiant si le paramètre
est égal à une valeur particulière. Si c'est le cas, alors la fonction s'arrête en retournant une
valeur constante ; il n'y a pas d'appel récursif.
- Un ou plusieurs cas généraux. La fonction exécute ce(s) cas si le test du cas d'arrêt a été
négatif. S'il y a plusieurs cas généraux, un autre test détermine lequel utiliser. Les cas
généraux sont les cas dont la valeur du paramètre n'importe pas, et ils conduisent à un
appel récursif.
Donc,
-
-
cas d'arrêt signifie :"valeur particulière de n pour laquelle la fonction doit s'arrêter".
cas général signifie : "appel récursif si n ne satisfait pas la (ou les) condition(s) du (ou des)
cas d'arrêt".
Ce qu’il faut retenir :
Il faut impérativement respecter les deux règles suivantes lorsqu’on écrit une fonction récursive :
- Une fonction récursive doit être définie à l’aide d’une expression conditionnelle dont au
moins l’un des cas mène à une expression évaluable sans appel récursif. C’est la
condition d’arrêt.
- Quelque soit la valeur de (ou des) argument(s) de la fonction, il faut que la condition
d’arrêt soit atteinte en un nombre fini d’appels récursifs.
Notez que vos fonctions récursives peuvent très bien contenir plusieurs (n, par exemple) appels à
elle-même, on parlera alors de fonctions récursives d'ordre n. Par exemple, certains
algorithmes de tris sur des tableaux, dont le tri rapide, utilisent la récursivité.
Il est également possible de faire des fonctions récursives croisées :
Advertisement
Considérez une fonction A et une fonction B telles que A appelle B et B appelle A. C'est tout à
fait faisable en C, à moins d'avoir déclaré en tête du fichier source le prototype de la deuxième
fonction (sinon le compilateur renverra une erreur).
Ce genre de fonctions est plus difficile à concevoir, car il faut bien faire attention à prendre en
compte tous les cas.
1.3. Attention !!! L'oubli d'un cas d'arrêt est fatal:
Les fonctions récursives peuvent être très pratiques, comme nous l'avons vu. Mais elles peuvent
aussi se révéler désastreuses si on en fait un mauvais usage.
Exemples :
Voyons un premier exemple de fonction récursive vérolée :
void fonction( )
{
fonction( );
}
int main( )
{
fonction();
return 0;
}
(cid:1) Il n'y a pas de cas d'arrêt !!!
Voyons un deuxième exemple :
void fonction( )
{
fonction( );
fonction( );
}
Moralité
Advertisement
Vérifiez toujours vos cas d'arrêts dans vos fonctions récursives. Regardez bien s'ils ont une
chance d'être atteint pour éviter les problèmes ; et essayez d'évaluer le nombre maximal ou au
moins le nombre moyen d'appels qui sera effectué par votre fonction en limitant le paramètre à
une valeur maximale.
2. Autres exemples
Exercice 1 : (Somme des premiers entiers)
Ecrire deux fonctions C,
l’autre un algorithme
récursif,permettant de calculer, l’entier naturel n étant donné en entrée, la somme des n premiers
entiers naturels non nuls.
l’une utilisant un algorithme
itératif,
Exercice 2 : (Somme des puissances cinquièmes des premiers entiers)
Ecrire deux fonctions C, l’une utilisant un algorithme itératif, l’autre un algorithme récursif,
permettant de calculer, l’entier naturel n étant donné en entrée, la somme des n premiers entiers
naturels non nuls à la puissance cinq.
Exercice 3
Ecrire deux fonctions C, l’une utilisant un algorithme itératif, l’autre un algorithme récursif,
permettant de calculer, l’entier naturel n étant donné en entrée, la somme 1 × 2 + 2 ×3 + 3 × 4
+ . . . + n × (n + 1).
Exercice 4 : (Exponentiation)
Ecrire une fonction C, utilisant un algorithme récursif, permettant de calculer la puissance xn,
avec x réel et n entier naturel.