Рекурсия

— Привет, Амиго. Сегодня Билаабо расскажет тебе, что такое рекурсия.

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

— Ок. Вроде понял. Спасибо, Билаабо.