Rekursi

"Hai, Amigo. Hari ini Bilaabo akan memberitahu anda tentang rekursi."

Seperti yang anda ketahui, di Jawa beberapa kaedah memanggil kaedah lain. Selain itu, apabila kaedah dipanggil, hujah khusus dihantar kepadanya, tetapi pembolehubah setempat kaedah mengambil nilai tertentu semasa ia dijalankan.

"Uh huh."

"Dan seperti yang anda ketahui, pembolehubah dalaman kaedah yang berbeza adalah bebas antara satu sama lain."

"Uh huh."

"Jadi bayangkan keadaan di mana kaedah memanggil dirinya sendiri. Ini dipanggil rekursi. Contohnya:"

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!

"Saya dapat melihat bahawa kaedah itu memanggil dirinya dalam kod, tetapi saya secara jujur ​​tidak faham apa yang berlaku."

"Nah, tentang perkara yang sama yang berlaku apabila kaedah yang berbeza dipanggil."

"Tidak, saya bertanya tentang apa yang berlaku dengan pembolehubah? Dengan nilai mereka? Dan bagaimana kita keluar dari kaedah itu? Atau adakah kita keluar semuanya sekaligus?"

"Kebaikan yang baik. Semuanya lebih mudah. ​​Bayangkan bahawa kaedah yang memanggil dirinya telah didarab berkali-kali. Kemudian kita akan mempunyai situasi yang serupa:"

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!

"Dengan kata lain, setiap kali kaedah dipanggil (walaupun dengan sendirinya), pembolehubah baharu dicipta yang menyimpan data untuk kaedah ini. Tiada pembolehubah dikongsi."

"Dengan setiap panggilan, satu lagi salinan argumen kaedah, dengan nilai baharu, dicipta dalam ingatan. Apabila kita kembali kepada kaedah lama, pembolehubahnya digunakan di sana. Dalam erti kata lain, semasa rekursi kita sebenarnya memanggil kaedah lain, tetapi dengan kod yang sama dengan kod kami! "

"Saya faham. Dan bagaimana cara keluar dari kaedah sedemikian berfungsi? Mungkin satu contoh?"

"OK. Satu contoh bernilai seribu perkataan. "Ini contoh anda:"

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. Saya rasa saya faham. Kenapa kita perlukan rekursi?"

"Terdapat banyak, banyak tugas yang boleh dibahagikan kepada subtugas berasingan yang sama dengan tugas asal. Contohnya, anda perlu menelusuri semua elemen pepohon XML. Setiap elemen boleh mempunyai beberapa elemen anak, dan ia mempunyai unsur anak sendiri."

"Atau anda perlu memaparkan senarai fail yang berada dalam direktori dan semua subdirektorinya. Jadi anda menulis kaedah yang memaparkan fail direktori semasa. Kemudian untuk mendapatkan fail semua subdirektori, anda memanggil kaedah anda menggunakan hujah yang berbeza: subdirektori."

"Sebagai contoh:"

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

"Baris 8 – Kami mendapat senarai semua fail (dan direktori) dalam direktori dir."

"Barisan 10-11 – Jika fail itu sebenarnya direktori, maka kami memanggil printAllFiles sekali lagi, tetapi kali ini dengan hujah lain: subdirektori."

"Barisan 13 – Kami memaparkan nama fail semasa."

"OK. Saya rasa saya faham. Terima kasih, Bilaabo."