Herhaling

"Hallo, Amigo. Vandaag vertelt Bilaabo je over recursie."

Zoals u weet, roepen sommige methoden in Java andere methoden aan. Bovendien, wanneer een methode wordt aangeroepen, worden er specifieke argumenten aan doorgegeven, maar de lokale variabelen van de methode nemen bepaalde waarden aan terwijl deze wordt uitgevoerd.

"Uh Huh."

"En zoals u weet, zijn de interne variabelen van verschillende methoden onafhankelijk van elkaar."

"Uh Huh."

"Dus stel je de situatie voor waarin een methode zichzelf aanroept. Dit wordt recursie genoemd. Bijvoorbeeld:"

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!

"Ik zie dat de methode zichzelf aanroept in de code, maar ik begrijp eerlijk gezegd niet wat er gebeurt."

"Nou, ongeveer hetzelfde wat er gebeurt als een andere methode wordt aangeroepen."

"Nee, ik vraag wat er met de variabelen gebeurt? Met hun waarden? En hoe verlaten we de methode? Of sluiten we alles in één keer af?"

"Goeie genade. Het is allemaal veel eenvoudiger. Stel je voor dat de methode die zichzelf aanroept vele malen is vermenigvuldigd. Dan zouden we de analoge situatie hebben:"

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!

"Met andere woorden, elke keer dat een methode wordt aangeroepen (zelfs op zichzelf), worden er nieuwe variabelen gemaakt die de gegevens voor deze methode opslaan. Er zijn geen gedeelde variabelen."

"Bij elke aanroep wordt een andere kopie van de methode-argumenten, met nieuwe waarden, in het geheugen gemaakt. Wanneer we terugkeren naar de oude methode, worden de variabelen daar gebruikt. Met andere woorden, tijdens recursie roepen we eigenlijk een andere methode aan, maar met de dezelfde code als de onze! "

"Ik snap het. En hoe werkt het verlaten van zulke methodes? Misschien een voorbeeld?"

"OK. Een voorbeeld zegt meer dan duizend woorden. "Hier is jouw voorbeeld:"

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. Ik denk dat ik het begrijp. Waarom hebben we recursie nodig?"

"Er zijn heel veel taken die kunnen worden onderverdeeld in afzonderlijke subtaken die identiek zijn aan de oorspronkelijke taak. Je moet bijvoorbeeld door alle elementen van een XML-boom lopen. Elk element kan verschillende onderliggende elementen hebben en ze hebben hun eigen onderliggende elementen."

"Of u moet de lijst met bestanden in een map en al zijn submappen weergeven. U schrijft dus een methode die de bestanden van de huidige map weergeeft. Om vervolgens de bestanden van alle submappen te krijgen, roept u uw methode aan met behulp van een ander argument: een submap."

"Bijvoorbeeld:"

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());
 }
}

"Lijn 8 – We krijgen de lijst met alle bestanden (en mappen) in de map dir."

"Regels 10-11 – Als het bestand eigenlijk een directory is, dan noemen we printAllFiles opnieuw, maar deze keer met een ander argument: de subdirectory."

"Regel 13 - We geven de naam van het huidige bestand weer."

"Oké. Ik denk dat ik het begrijp. Dank je, Bilaabo."