Les fonctions récursives ont un emploi très particulier, il ne faut pas les utiliser n'importe comment car elles utilisent la pile mémoire (stack) et en cas de plantage peuvent avoir des conséquences sur d'autres programmes. La récursivité en elle même se défini par son auto-appellation, c'est à dire que c'est quelque chose qui se reproduit sur lui même. Par exemple quelqu'un qui se remet en cause, utilise un raisonnement récursif, car il s'auto-analyse. On parle alors d'algorithme récursif. L'algorithme étant une capacité de raisonner.





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.





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  
 




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
  }                                   //
} 




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


 
Mots clés :  
  c 
  
  system 
    >   Articles connexes :

Comment gagner du temps sur Internet

Comment gagner du temps sur Internet



/tmp et /var/log en noexec sur macOS

/tmp et /var/log en noexec sur macOS


4880920