recursão

"Oi, amigo. Hoje o Bilaabo vai falar sobre recursão."

Como você sabe, em Java alguns métodos chamam outros métodos. Além disso, quando um método é chamado, argumentos específicos são passados ​​para ele, mas as variáveis ​​locais do método assumem determinados valores durante sua execução.

"Uh-huh."

"E como você sabe, as variáveis ​​internas dos diferentes métodos são independentes umas das outras."

"Uh-huh."

"Então, imagine a situação em que um método chama a si mesmo. Isso é chamado de recursão. Por exemplo:"

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!

"Posso ver que o método chama a si mesmo no código, mas sinceramente não entendo o que está acontecendo."

"Bem, quase a mesma coisa que acontece quando um método diferente é chamado."

"Não, estou perguntando sobre o que acontece com as variáveis? Com ​​seus valores? E como saímos do método? Ou saímos de tudo de uma vez?"

"Meu Deus. É tudo muito mais simples. Imagine que o método que chama a si mesmo foi multiplicado muitas vezes. Então teríamos a situação análoga:"

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!

"Em outras palavras, cada vez que um método é chamado (mesmo sozinho), são criadas novas variáveis ​​que armazenam os dados desse método. Não há variáveis ​​compartilhadas."

"A cada chamada, outra cópia dos argumentos do método, com novos valores, é criada na memória. Quando voltamos ao método antigo, suas variáveis ​​são usadas lá. Ou seja, durante a recursão na verdade chamamos outro método, mas com o mesmo código que o nosso! "

"Entendo. E como funciona a saída desses métodos? Talvez um exemplo?"

"OK. Um exemplo vale mais que mil palavras. "Aqui está o seu exemplo:"

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

"OK. Acho que entendi. Por que precisamos de recursão?"

"Existem muitas, muitas tarefas que podem ser divididas em subtarefas separadas que são idênticas à tarefa original. Por exemplo, você precisa percorrer todos os elementos de uma árvore XML. Cada elemento pode ter vários elementos filhos, e eles têm seus próprios elementos filhos."

"Ou você precisa exibir a lista de arquivos que estão em um diretório e todos os seus subdiretórios. Então você escreve um método que exibe os arquivos do diretório atual. Então, para obter os arquivos de todos os subdiretórios, você chama seu método usando um argumento diferente: um subdiretório."

"Por exemplo:"

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

"Linha 8 – Obtemos a lista de todos os arquivos (e diretórios) no diretório dir."

"Linhas 10-11 – Se o arquivo for realmente um diretório, então chamamos printAllFiles novamente, mas desta vez com outro argumento: o subdiretório."

"Linha 13 – Exibimos o nome do arquivo atual."

"OK. Acho que entendi. Obrigado, Bilaabo."