Rekurzió

"Szia, Amigo. Ma Bilaabo mesél neked a rekurzióról."

Mint tudják, a Java-ban bizonyos módszerek más módszereket hívnak. Ezenkívül a metódus meghívásakor adott argumentumok kerülnek átadásra, de a metódus helyi változói bizonyos értékeket vesznek fel futás közben.

"UH Huh."

"És mint tudod, a különböző módszerek belső változói függetlenek egymástól."

"UH Huh."

"Így képzeld el azt a helyzetet, amikor egy metódus meghívja magát. Ezt rekurziónak hívják. Például:"

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!

"Látom, hogy a módszer meghívja magát a kódban, de őszintén szólva nem értem, mi történik."

– Nos, körülbelül ugyanaz, ami akkor történik, ha egy másik módszert hívnak meg.

"Nem, azt kérdezem, hogy mi történik a változókkal? Az értékükkel? És hogyan lépjünk ki a metódusból? Vagy egyszerre lépjünk ki mindenből?"

"Jó isten. Sokkal egyszerűbb az egész. Képzeld el, hogy a magát hívó metódust sokszor megsokszorozták. Akkor analóg helyzetünk lenne:"

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!

"Más szóval, minden alkalommal, amikor egy metódust meghívnak (akár önmagában is), új változók jönnek létre, amelyek az ehhez a metódushoz tartozó adatokat tárolják. Nincsenek megosztott változók."

"Minden hívással a metódus argumentumainak egy újabb, új értékekkel rendelkező másolata jön létre a memóriában. Ha visszatérünk a régi metódushoz, ott annak változóit használjuk. Vagyis a rekurzió során tulajdonképpen egy másik metódust hívunk meg, de a ugyanaz a kód, mint a miénk! "

"Értem. És hogyan működik az ilyen módszerek kilépése? Talán egy példa?"

"OK. Egy példa többet ér ezer szónál. "Íme a példád:"

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

"Rendben. Azt hiszem, értem. Miért van szükségünk rekurzióra?"

"Sok-sok feladat van, amelyeket külön részfeladatokra lehet osztani, amelyek megegyeznek az eredeti feladattal. Például egy XML-fa összes elemét végig kell járni. Minden elemnek több gyermekeleme lehet, és ezeknek megvan a sajátjuk. saját gyermekelemek."

"Vagy meg kell jelenítenie a könyvtárban található fájlok listáját és az összes alkönyvtárát. Tehát ír egy metódust, amely megjeleníti az aktuális könyvtár fájljait. Ezután az összes alkönyvtár fájljainak lekéréséhez hívja meg a metódusát egy más argumentum: egy alkönyvtár."

"Például:"

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

"8. sor – Megkapjuk a dir könyvtárban lévő összes fájl (és könyvtár) listáját."

"10-11. sor – Ha a fájl valójában egy könyvtár, akkor ismét meghívjuk a printAllFiles-t , de ezúttal egy másik argumentummal: az alkönyvtárral."

"13. sor – Megjelenítjük az aktuális fájl nevét."

"Rendben. Azt hiszem, értem. Köszönöm, Bilaabo."