Plan du site  
pixel
pixel

Articles - Étudiants SUPINFO

Structures de données: La récursivité

Par Seifeddine AMMAR Publié le 14/02/2020 à 20:48:38 Noter cet article:
(0 votes)
Avis favorable du comité de lecture

Cet article est une traduction de mon article "Data Structures : Recursion" disponible sur : https://www.supinfo.com/articles/single/10462--data-structures-recursion

Qu'est-ce que la récursivité?

La signification littérale du mot Récursion est auto-appel , et ce seul sens suffit pour le définir . Simplement c'est un type de méthode qui fait appelle à elle-même. Cette méthode a une structure et des bases qui doivent être implémentées dans cette méthode .

Structure générale des méthodes de récursivité

public void Test1 (int i) {
  
    // Lignes de code
  
    si(){
        // la condition de base ou le cas qui arrête l'auto-appel
      }
    Test1 (/ * toute valeur à passer * /); // le self call

  // Lignes de code
} 

La chose importante qui ne doit pas être oubliée est la condition de base. C'est une condition qui met fin à l'auto-appel de la méthode. Cette condition est similaire à celle que nous mettons pour sortir d'une boucle.

Si cette condition n'est pas remplie, nous serons face à un appel sans fin qui entraînera une surcharge mémoire avant le 'breakdown' de l'application.

Pour mieux comprendre la signification de la récursivité , examinons quelques exemples:

Etudes d'exemples

1) Factorielle (X!):

Factorielle (X) est la somme de la multiplication de tous les nombres de 1 à X. Ce problème de calcul peut être simplement résolu par récursivité comme indiqué ci-dessous :

   
    public  int  Factorial (int x){
        
        if(x == 0){
                    return 1;
                  }     
        else {
                return  x *  Factorial (x-1);
             }
    }
    
    

Cette méthode prend un entier (int) en entrée et donne un autre entier en sortie.

D'abord , nous devons déterminer le cas de base . Dans cet exemple, ce sera lorsque le nombre multiplié est 0 alors le résultat est 1. Ce qui signifie que lorsque 0 est envoyé à la méthode, la sortie sera 1.

Si la méthode ne reçoit pas de 0 , la méthode suivra l'autre option . La valeur de i sera stockée et multipliée par sa précédente

 x * (x + 1) 

avec 'i' étant la valeur actuelle de 'x' et 'x + 1' c'est la valeur précédente puisque nous soustrayons 1 pour chaque itération.

La méthode s'appellera alors à nouveau avec une mise à jour 'x-1'. Cette mise à jour est cruciale sinon la méthode continuera à s'appeler pour toujours car elle ne pourra pas remplir la condition requise pour arrêter la boucle. Cette condition n'est remplie que lorsque:

 x == 0 

Regardons cet exemple pour clarifier les choses. Supposons que nous avons appelé méthode comme celle-ci:

 System.out.println (Factorial (4)); 

Dans le premier appel 4! = 0, nous suivons donc l'étape suivante:

 4 * Factorielle (4-1) 

Deuxième appel nous donnera ceci résultat:

 3 * Factorial (4-1) 

Ensuite, troisième appel :

 2 * Factorial (2-1) 

Et enfin, le quatrième appelez :

 1 * Factorial (1-1) 

Lors du cinquième appel, i == 0, donc notre condition est remplie . La valeur 1 sera retourné au dernier appel.

Une des choses à garder à l’esprit, c’est que si la méthode s’appelle plusieurs fois, les appels seront être conservé dans une pile de sorte que le dernier appel obtient la première réponse . Jetons un œil à la figure ci-dessous:

2) Somme de X:

Comme nous l'avons fait dans l'exemple précédent, nous allons créer une méthode qui prend un valeur entière ('X') et calculer la somme de tous les nombres de 0 à X.

    public int SUM (int x)
    {
      si (x == 0)
        {
        retourner 0;
        }
      autre
         {
         retourne x + SUM (x -1);
         }
     }
                

3) Affichage des nombres:

Ici, l'utilisateur sélectionne la valeur de X et nous afficherons la suite des nombres de X à 1 dans un ordre décroissant

    public void printInt (int x)
    {
      si (x == 1)
        {
        System.out.println (1);
        }
      autre
        {
        System.out.println (x);
        printInt (x-1);
        }
    }
                

Cependant, si nous voulions afficher les chiffres dans un ordre croissant. Il suffit de changer l'ordre des 2 dernières lignes comme indiqué ci-dessous:

    public void printInt (int x)
    {
      si (x == 1)
        {
        System.out.println (1);
        }
      autre
        {
        printInt (x-1);
        System.out.println (x);
        }
    }
                

Conclusion

L'utilisation de la récursivité dans un algorithme a à la fois avantages et inconvénients . Le principal avantage est la simplicité de instructions , tandis que l'inconvénient est que récursif les algorithmes peuvent être mémoire consommant , ce qui les rend peu pratiques pour les instances plus importantes.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Toeic, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels