récursivité

"Salut, Amigo. Aujourd'hui, Bilaabo va te parler de la récursivité."

Comme vous le savez, en Java, certaines méthodes appellent d'autres méthodes. De plus, lorsqu'une méthode est appelée, des arguments spécifiques lui sont transmis, mais les variables locales de la méthode prennent certaines valeurs pendant son exécution.

"Euh-huh."

"Et comme vous le savez, les variables internes des différentes méthodes sont indépendantes les unes des autres."

"Euh-huh."

"Alors imaginez la situation où une méthode s'appelle elle-même. C'est ce qu'on appelle la récursivité. Par exemple :"

public static void main(String[] args)
{
 countDown(10);
}

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

10
9
8
7
6
5
4
3
2
1
Boom!

"Je peux voir que la méthode s'appelle elle-même dans le code, mais honnêtement, je ne comprends pas ce qui se passe."

"Eh bien, à peu près la même chose qui se produit lorsqu'une méthode différente est appelée."

« Non, je demande ce qui se passe avec les variables ? Avec leurs valeurs ? Et comment sort-on de la méthode ? Ou quitte-t-on tout d'un coup ? »

"Bon Dieu. Tout est beaucoup plus simple. Imaginez que la méthode qui s'appelle elle-même ait été multipliée plusieurs fois. Nous aurions alors la situation analogue :"

public static void main(String[] args)
{
 countDown(10);
}

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

public static void main(String[] args)
{
 countDown1(10);
}

public static void countDown1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown2(x - 1);
 }
}
public static void countDown2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown3(x - 1);
 }
}
public static void countDown3(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown4(x - 1);
 }
}

public static void countDown4(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown5(x - 1);
 }
}

3
2
1
Boom!

3
2
1
Boom!

"En d'autres termes, chaque fois qu'une méthode est appelée (même par elle-même), de nouvelles variables sont créées qui stockent les données de cette méthode. Il n'y a pas de variables partagées."

"A chaque appel, une autre copie des arguments de la méthode, avec de nouvelles valeurs, est créée en mémoire. Lorsque nous revenons à l'ancienne méthode, ses variables y sont utilisées. En d'autres termes, lors de la récursivité, nous appelons en fait une autre méthode, mais avec le même code que le nôtre ! "

"Je vois. Et comment sortir de telles méthodes fonctionne-t-il? Peut-être un exemple?"

"OK. Un exemple vaut mille mots. "Voici votre exemple :"

public static void main(String[] args)
{
 print(3);
}

public static void print(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print(x - 1);
  System.out.println(x);
 }
}

public static void main(String[] args)
{
 print1(3);
}

public static void print1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print2(x - 1);
  System.out.println(x);
 }
}

public static void print2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print3(x - 1);
  System.out.println(x);
 }
}

…

3
2
1
Boom!
1
2
3

3
2
1
Boom!
1
2
3

"OK. Je pense avoir compris. Pourquoi avons-nous besoin de la récursivité ?"

"Il existe de très nombreuses tâches qui peuvent être divisées en sous-tâches distinctes identiques à la tâche d'origine. Par exemple, vous devez parcourir tous les éléments d'une arborescence XML. Chaque élément peut avoir plusieurs éléments enfants, et ils ont leur propre propres éléments enfants."

"Ou vous devez afficher la liste des fichiers qui se trouvent dans un répertoire et tous ses sous-répertoires. Vous écrivez donc une méthode qui affiche les fichiers du répertoire courant. Ensuite, pour obtenir les fichiers de tous les sous-répertoires, vous appelez votre méthode à l'aide d'un argument différent : un sous-répertoire."

"Par exemple:"

public static void main(String[] args)
{
 printAllFiles(new File("c:/windows/"));
}

public static void printAllFiles(File dir)
{
 for (File file : dir.listFiles())
 {
  if (file.isDirectory())
   printAllFiles(file);
  else
   System.out.println(file.getAbsolutePath());
 }
}

"Ligne 8 - Nous obtenons la liste de tous les fichiers (et répertoires) dans le répertoire dir."

"Lignes 10-11 - Si le fichier est en fait un répertoire, nous appelons à nouveau printAllFiles , mais cette fois avec un autre argument : le sous-répertoire."

"Ligne 13 - Nous affichons le nom du fichier en cours."

"OK. Je pense avoir compris. Merci, Bilaabo."