c 0x01. FACTORIELLE
En informatique une fonction récursive est une fonction qui s'appelle toute seule. Le résultat temporaire est dans la pile et est donc retourné une fois que la condition de retour de la fonction est remplie. On ne peut pas comparer une simple boucle avec une fonction récursive, d'un point de vue algorithmique c'est complètement différent. D'ailleurs la lecture humaine d'une fonction récursive et d'une boucle n'ont rien à voir, jugez par vous-même.
/*- Operation factorielle, en recursif ---------------------------------------*/ int factorielle(int n) { printf("/nx %d",n); if(n==1) // on multiplie les éléments entre eux return n; // tant qu'on est pas à 1 de telle sorte que else // le resultat soti égal à return n*factorielle(n-1); // 1*2*3*4* ... *n = n! }
Nous pouvons lire la fonction de manière mathématique, comme suit. C'est à dire que la factorielle(n) est égal à la factorielle(n-1) multiplié par n. La fonction factorielle s'appelle toute seule pour donner le résultat, puisque n est égal à n multiplié par la factorielle de 1, lorsque n vaut 1. On peut donc tout faire avec une seule fonction.
a = a x a x a x a x a
n n-4 n-3 n-2 n-1
autrement dit :
5! = 4! x 5 5 x 4 x 3 x 2 x 1 = (4 x 3 x 2 x 1) x 5
4! = 3! x 4 ...
3! = 2! x 3 3 x 2 x 1 = (2 x 1) x 3
2! = 1! x 2 ...
1! = 1! x 1 1 = 1 On voit bien que la fonction factorielle se répète sur elle même. On peut donc lire la fonction de la manière suivante :
je multiplie les éléments tant que ma valeur n'est pas 1
L'important est que "tant que" ne se lit pas dès le début.
0x02. SIGMA
De même que pour la fonction ci-dessus on utilise la récursivité pour la fonction 'Sigma', qui représente la somme depuis 0 jusqu'à l'élément N. Elle contient elle même le résultat puisque la somme de 0 à n est égal à la somme de n plus 0, donc la somme de 0 égal à la somme de 0 plus 0. Pour ce genre de fonction, (factorielle et somme) il faut connaitre l'élément neutre du domaine dans lequel on travail. Le domaine est ici les entiers naturels représentable par |N (grand N majuscule, l'ensemble des entiers naturels).
/*- Operation sigma (somme de tout les chiffres) -----------------------------*/ int somme(int n) { printf("/n%+ d",n); if(n==0) // si on arrive à n==1 c'est qu'on a return n; // parcouru notre nombre depuis sa valeur jusqu'à else // 1 en l'additionnant à la fonction return n+somme(n-1); // sigma(n) = 1+2+3+4+ ... +n }
Pour cette une fonction récursive, ici dans le cas de la fonction Sigma, on pourrait représenter l'état de la pile en mémoire ainsi:
ETAT
+----------+
// | |
|| +----------+ 14 + 1 |
P || | | = |
|| +----------+ 12 + 2 | 15 |
I || | | = | |
|| +----------+ 9 + 3 | 14 | |
L || | | = | | |
|| | 5 + 4 | 12 | | |
E || | = | | | |
// | 9 | | | |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| | | |
Sigma(5) = Sigma(4) + 5 | | |
Sigma(4) = Sigma(3) + 4 | |
Sigma(3) = Sigma(2) + 3 |
Sigma(2) = Sigma(1) + 2
Sigma(1) = Sigma(0) + 1
0x03. LISTE CHAINEES
Pour les déclarations et initialisation d'une liste chainée voire le tutoriel correspondant : ici. On peut très bien imaginer une fonction récursive pour le parcours d'une liste cha?née, car effectivement le parcours se fait à l'aide d'un pointeur temporaire qui devient à chaque élément suivant sa nouvelle tête. Si on considère que la lecture se fait à partir de la tête et que pendant la lecture on passe à l'élément suivant alors notre pointeur va parcourir toute la liste. L'élément neutre étant l'élément NULL puisqu'un ce n'est pas une tête, mais un élément final. Dans ce cas on peut dire que le parcours se fait de cette manière :
a -> suivant -> suivant -> suivant = NULL
p
lecture(p) : p = p -> suivant
-------------------------------------------------------------------------------
a -> suivant -> suivant -> suivant = NULL
p
lecture(p) : p = p -> suivant
-------------------------------------------------------------------------------
a -> suivant -> suivant -> suivant = NULL
p
lecture(p) : p = p -> suivant
-------------------------------------------------------------------------------
a -> suivant -> suivant -> suivant = NULL
p
lecture(p) : p
p -> suivant = NULL
-------------------------------------------------------------------------------
a -> suivant -> suivant -> suivant = NULL
p
Le point d'arrêt est définit ici, c'est à dire quand la variable 'p' vaut NULL La fonction récursive est bien déssinée, tant que p n'est pas NULL on lit le suivant :
parcourir_liste(p est un pointeur vers une liste)
{
si( p vaut l'élément NULL )
{
alors retourner( p );
}
sinon
{
parcourir_liste( l'élément suivant de p );
}
} Et voici ce que ça donne en langage C:
NB: la variable "static int i;" ne sert qu'à compter les éléments de la liste, elle est purement optionnelle. Une variable statique est une variable dont l'emplacement mémoire ne change pas.
/*- Lit la liste en récursif -------------------------------------------------*/ LISTE* lire_liste(LISTE* l) // Exemple de fonction { // recursive qui lit tout les static int i; // éléments d'une liste chainee if(l->suivant==NULL) // { // return l; // lire_list(l->suivant) } // else // { // rapelle la fonction avec printf("/n%d : %d",++i,l->nbr); // l = l->suivant lire_liste(l->suivant); // jusqu'à ce que l->suivant == NULL } // }
0x04. CONCLUSION
Les fonctions récursives sont terriblement utiles en réalité notamment pour le parcours d'arbre et de fôret. C'est cette technique qui est utilisée par les correcteurs orthographique. Par contre d'un point de vue sécurité il n'y a rien de pire. Pour ce propos, je vous renvoie sur l'article de GITS concernant les fonctions récursives.
=> Écrit par : Nicolas, le 05 décembre 2007
