Rekursiya

— Salom, Amigo. Bugun Bilaabo senga rekursiya nima ekanligini tushuntiradi.

Bilganingdek, Javada ba'zi metodlar boshqa metodlarni chaqiradi. Shu bilan birga, metod chaqirilganda, unga aniq argumentlarning qiymatlari beriladi, va uning ishlashi davomida, metodning lokal o'zgaruvchilari ma'lum bir qiymatlarni oladi.

— Ha, tushunarli.

— Va yana bilganingdek, turli metodlarning ichki o'zgaruvchilari bir-biridan mustaqil.

— Ha, tushunarli.

— Shunday, mana, metod o'z-o'zini chaqira oladigan vaziyatni tasavvur qiling. Aynan shunday holat rekursiya deb ataladi. Misol:

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!

— Rostini aytsam, metod kodda o'z-o'zini chaqirayotganini ko'ryapman, lekin nima sodir bo'layotganini tushunmayapman.

— Ha, boshqa metod chaqirilgandagi holatga o'xshash.

— Yo'q, men o'zgaruvchilarga nima sodir bo'layotganini so'rayapman? Ularning qiymatlari? Va biz metoddanga qanday chiqamiz? Yoki biz hammasidan birdan chiqamizmi?

— Xudo asrasin. Ha, bu osonroq. Metod o'zini ko'p marotaba nusxalashni tasavvur qiling. Bu holda shunday vaziyat bo'ladi:

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!

Ya'ni, har safar metod chaqirilganda (o'z-o'zini chaqirishda ham) yangi o'zgaruvchilar yaratiladi, bu metod uchun ma'lumotlarni saqlaydigan. Umumiy o'zgaruvchilar yo'q.

Har safar chaqirilganda xotirada metodning yangi argumentlari nusxasi paydo bo'ladi, lekin allaqachon yangi qiymatlari bilan. Eski metodga qaytish vaqtida, u yerdagi o'zgaruvchilar ishlatiladi. Ya'ni rekursiyada aslida biz boshqa metodni chaqiramiz, lekin kodimiz bilan bir xil!

— Tushunarli. Va bu metodlardan chiqish qanday ishlaydi? Misol keltira olasizmi?

— Yaxshi. Bir misol ming so'zga arziydi. Mana senga misol:

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. Tushundim. Nega rekursiya kerak?

— Juda ko'p muammolar bor, ular alohida kichik vazifalarga bo'linadi, dastlabki vazifaga o'xshash. Masalan, XML-daraxtidagi barcha elementlarni aylanib chiqish kerak. Har bir elementning bir nechta farzand elementi bo'lishi mumkin, ularda esa o'zlari.

Yoki sizga katalogdagi va barcha ichki kataloglardagi fayllar ro'yxatini chiqarish kerak. Shunda siz hozirgi katalogdagi fayllarni chiqaradigan metod yozasiz, keyin barcha ichki kataloglar fayllarini olish uchun uni o'zini yana chaqirasiz, lekin boshqa parametr bilan - ichki katalog bilan.

Misol:

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-qator – barcha fayllar ro'yxatini olamiz (va kataloglar) dir katalogida.

10-11 qatorlar – agar fayl aslida katalog bo'lsa, uning fayllarini chiqarish uchun yana printAllFiles chaqiramiz, lekin boshqa parametr bilan - ichki katalog bilan.

13-qator – hozirgi fayl nomini chiqaramiz.

— Ok. Tushundim. Rahmat, Bilaabo.