Рекурсія

— Привіт, Аміго. Сьогодні говоримо про рекурсію.

Як ти знаєш, у Java одні методи викликають інші методи. При цьому, при виклику методу передаються конкретні значення аргументів, а під час його роботи локальні змінні методи набувають деяких значень.

— Так.

— І, як ти знаєш, внутрішні змінні різних методів незалежні одна від одної.

— Ага.

— Так ось, уяви ситуацію, коли метод може викликати сам себе. Саме вона називається рекурсією. Приклад:

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!

— Чесно кажучи, бачу, що метод у коді сам себе викликає, але не розумію, що саме при цьому відбувається.

— Так приблизно те саме, що й при виклику іншого методу.

— Ні, я питаю, що відбувається зі змінними? З їхніми значеннями? І як ми виходимо із методу? Чи ми виходимо з усіх одразу?

— Та все набагато простіше. Уяви, що метод, який викликає сам себе, розмножили багато разів. Тоді буде аналогічна ситуація:

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

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

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!

Тобто кожного разу при виклику методу (навіть самого себе) створюються нові змінні, які зберігають дані для цього методу. Жодних загальних змінних немає.

При кожному виклику у пам'яті з'являється ще одна копія аргументів методу, але вже з новими значеннями. При поверненні в старий метод там використовуються його змінні. Тобто, при рекурсії фактично ми викликаємо інший метод, але з таким же кодом, як в нашому!

— Зрозуміло. А як працює вихід із цих методів? Чи можна приклад?

— Гаразд. Один приклад коштує тисячі слів. Ось тобі приклад:

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 – виводимо ім'я поточного файлу.

— Ок. Начебто зрозуміло.