Рекурсия

Модул 2: Java Core
Ниво , Урок
На разположение

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

Рекурсия - 1

Както знаете, в 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 – Показваме името на текущия файл.“

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

Коментари
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION