Cours algorithmique 2 : la recursivite
Télécharger-
Cours algorithmique 2 : la récursivité
1) Domaines d'utilisation :
La récursivité est une notion provenant des mathématiques.
Pour la programmation, on a besoin de connaître la récursivité pour :
. comprendre le tri rapide (Quick Sort) ;
. comprendre l'arbre binaire dont 90 % du traitement est récursif.
Il est rare qu'un programmeur doive écrire lui-même une fonction récursive. Cependant, il est profitable d'être capable d'écrire des fonctions récursives simples et de les simuler pour comprendrele principe.
2) Définition :
En pratique, une fonction est récursive si elle s'appelle elle-même.
exemple : int factoriel ( int n )
{
if ( n <= 1 )
return 1 ;
else
return n * factoriel(n-1) ;
}
3) Conseils d'écriture d'une fonction récursive :
Ces conseils sont illustrés par l'exemple suivant :
Écrire une fonction récursive permettant de calculer la somme des chiffres d'un entier n positif (exemple : n = 528, la somme des chiffres de n est 15).
1. Observer le problème afin de :
a) décrire la condition d'arrêt : quand peut-on trouver 'facilement' la solution ?
(une solution triviale) :
Si on a le choix entre n = 528 et n = 8, il est certain qu'on choisit n = 8. La somme des chiffres de 8 est 8.
Conclusion : Si n a un seul chiffre, on arrête. La somme des chiffres est n lui-même.
if ( n < 10 ) return n;
b) de réduire le problème à un problème d'ordre inférieur pour que la condition d'arrêt soit atteinte un moment donné :
somChif(528) 8 + somChif(52)
8 + ( 2 + somChif(5) )
8 + 2 + 5
D'un problème de 3 chiffres, on réduit d'abord à un problème de deux chiffres : somChif(52). Celui-ci est réduit à celui d'un seul chiffre : somChif(5).
On rencontre la condition d'arrêt.
else
return n % 10 + somChif ( n / 10 ) ;
2. Écriture de la fonction :
int somChif ( int n )
{
if ( n < 10 ) /* condition d'arrêt */
return n;
else
/* réduction du problème : */
return n % 10 + somChif ( n / 10 ) ;
}
Exercice :
Illustrer les conseils précédents pour écrire une fonction récursive
qui permet de calculer le produit de deux entiers positifs a et b.
Notes :
1. Si vous avez le choix entre : 12 x 456 et 12 x 0
lequel des deux calculs est le plus simple ?
2. 12 x 9 = 12 + 12 + 12 + ... + 12 ( 9 fois )
= 12 + (12 + 12 + ... + 12) ( 8 fois)
= 12 + 12 x 8
etc ...
4) Simulation :
Ne pas utiliser les 'noms' des arguments. Il est préférable
d'utiliser les rangs de ces arguments (le premier paramètre,
le deuxième paramètre, etc ...)
Exemple 1 :
Soit la fonction récursive suivante :
int facto ( int n )
{
if ( n <= 1 ) return 1 ;
else
return n * facto(n-1) ;
}
Quel est la valeur de facto (3) ?
Exemple 1 :
Le paramètre (ici 3) est-il <= 1 ?
Non. On retourne :
3 * facto (2)
-------------------------------------
Le paramètre (ici 2) est-il <= 1 ?
Non. On retourne : 2 * facto(1)
---------------------
Le paramètre (ici 1)
est-il <= 1 ?
Oui. On retourne 1
Ainsi facto(2) vaut 2 * 1 = 2
et facto(3) = 3 * facto(2) vaut 6.
- Evaluation :
-
Total des Votes : 0 -
Soyez le premier à écrire un commentaire sur ce fichier!
Veuillez vous identifier ou vous enregistrer.