Рекурсия

„Здравей, Амиго. Днес Билаабо ще ти разкаже за рекурсията.“

Както знаете, в Java някои методи извикват други методи. Освен това, когато се извика метод, към него се предават специфични аргументи, но локалните променливи на метода приемат определени стойности, докато се изпълнява.

"Хм нали."

„И Howто знаете, вътрешните променливи на различните методи са независими една от друга.“

"Хм нали."

„Така че представете си ситуацията, в която метод се извиква сам. Това се нарича рекурсия. Например:“

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!

„Виждам, че методът се самоизвиква в codeа, но честно казано не разбирам Howво се случва.“

„Ами горе-долу същото, което се случва, когато се извика различен метод.“

"Не, питам Howво се случва с променливите? С техните стойности? И How да излезем от метода? Или да излезем от всичко наведнъж?"

„Божичко. Всичко е много по-просто. Представете си, че методът, който се самоизвиква, е умножен многократно. Тогава ще имаме аналогичната ситуация:“

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!

"С други думи, всеки път, когато се извиква метод (дори сам по себе си), се създават нови променливи, които съхраняват данните за този метод. Няма споделени променливи."

„С всяко извикване в паметта се създава друго копие на аргументите на метода с нови стойности. Когато се върнем към стария метод, неговите променливи се използват там. С други думи, по време на рекурсия ние всъщност извикваме друг метод, но с същият code като нашия! "

„Разбирам. И How работи излизането от такива методи? Може би пример?“

"ОК. Един пример струва хиляда думи. "Ето вашия пример:"

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

"ОК. Мисля, че разбирам. Защо ни е необходима рекурсия?"

„Има много, много задачи, които могат да бъдат разделени на отделни подзадачи, които са идентични с оригиналната задача. Например, трябва да преминете през всички елементи на XML дърво. Всеки елемент може да има няколко дъщерни елемента и те имат своите собствени дъщерни елементи."

„Или трябва да покажете списъка с файлове, които са в директория и всички нейни поддиректории. Така че пишете метод, който показва файловете на текущата директория. След това, за да получите файловете на всички поддиректории, вие извиквате вашия метод с помощта на различен аргумент: поддиректория."

"Например:"

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 – Получаваме списъка с всички файлове (и директории) в директорията dir.“

„Редове 10-11 – Ако файлът всъщност е директория, тогава отново извикваме printAllFiles , но този път с друг аргумент: поддиректорията.“

„Ред 13 – Показваме името на текущия файл.“

"ОК. Мисля, че разбирам. Благодаря ти, Билаабо."