Recursiune

"Bună, Amigo. Astăzi Bilaabo vă va spune despre recursivitate."

După cum știți, în Java unele metode numesc alte metode. În plus, atunci când o metodă este apelată, îi sunt transmise argumente specifice, dar variabilele locale ale metodei iau anumite valori în timp ce rulează.

"Uh-huh."

„Și după cum știți, variabilele interne ale diferitelor metode sunt independente una de cealaltă.”

"Uh-huh."

„Deci imaginați-vă situația în care o metodă se autoinvocă. Aceasta se numește recursie. De exemplu:”

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!

„Văd că metoda se numește singură în cod, dar sincer nu înțeleg ce se întâmplă.”

— Ei bine, cam același lucru care se întâmplă atunci când se cheamă o metodă diferită.

"Nu, întreb ce se întâmplă cu variabilele? Cu valorile lor? Și cum ieșim din metodă? Sau părăsim totul dintr-o dată?"

"Doamne, binevoitor. Totul este mult mai simplu. Imaginați-vă că metoda care se numește pe sine a fost multiplicată de multe ori. Atunci am avea situația analogă:"

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!

„Cu alte cuvinte, de fiecare dată când o metodă este apelată (chiar și singură), sunt create noi variabile care stochează datele pentru această metodă. Nu există variabile partajate.”

„La fiecare apel, se creează în memorie o altă copie a argumentelor metodei, cu valori noi. Când revenim la vechea metodă, variabilele acesteia sunt folosite acolo. Cu alte cuvinte, în timpul recursiunii numim de fapt o altă metodă, dar cu același cod ca al nostru! ”

"Înțeleg. Și cum funcționează ieșirea din astfel de metode? Poate un exemplu?"

"OK. Un exemplu valorează cât o mie de cuvinte. "Iată exemplul tău:"

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. Cred că înțeleg. De ce avem nevoie de recursivitate?"

„Există multe, multe sarcini care pot fi împărțite în subsarcini separate, care sunt identice cu sarcina originală. De exemplu, trebuie să parcurgeți toate elementele unui arbore XML. Fiecare element poate avea mai multe elemente copil și acestea au propriile elemente copil.”

„Sau trebuie să afișați lista fișierelor care se află într-un director și toate subdirectoarele acestuia. Deci scrieți o metodă care afișează fișierele directorului curent. Apoi, pentru a obține fișierele tuturor subdirectoarelor, apelați metoda folosind un argument diferit: un subdirector”.

"De exemplu:"

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

„Linia 8 – Primim lista tuturor fișierelor (și directoarelor) din directorul director.”

„Rândurile 10-11 – Dacă fișierul este de fapt un director, atunci apelăm din nou printAllFiles , dar de data aceasta cu un alt argument: subdirectorul.”

„Linia 13 – Afișăm numele fișierului curent.”

"OK. Cred că înțeleg. Mulțumesc, Bilaabo."