Recursion

"Hi, Amigo. Ngayon sasabihin sa iyo ni Bilaabo ang tungkol sa recursion."

Tulad ng alam mo, sa Java ang ilang mga pamamaraan ay tumatawag sa iba pang mga pamamaraan. Bilang karagdagan, kapag tinawag ang isang pamamaraan, ipinapasa dito ang mga partikular na argumento, ngunit ang mga lokal na variable ng pamamaraan ay kumukuha ng ilang mga halaga habang tumatakbo ito.

"Uh huh."

"At tulad ng alam mo, ang mga panloob na variable ng iba't ibang mga pamamaraan ay independiyente sa isa't isa."

"Uh huh."

"Kaya isipin ang sitwasyon kung saan tinatawag ng isang pamamaraan ang sarili nito. Ito ay tinatawag na recursion. Halimbawa:"

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!

"Nakikita ko na ang pamamaraan ay tumatawag sa sarili nito sa code, ngunit sa totoo lang hindi ko maintindihan kung ano ang nangyayari."

"Buweno, tungkol sa parehong bagay na nangyayari kapag tinawag ang ibang pamamaraan."

"Hindi, tinatanong ko kung ano ang nangyayari sa mga variable? Sa kanilang mga halaga? At paano tayo lalabas sa pamamaraan? O lalabas ba tayo ng lahat nang sabay-sabay?"

"Goodness gracious. Mas simple ang lahat. Isipin na ang pamamaraan na tumatawag sa sarili nito ay pinarami nang maraming beses. Pagkatapos ay magkakaroon tayo ng kahalintulad na sitwasyon:"

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!

"Sa madaling salita, sa tuwing tatawagin ang isang pamamaraan (kahit sa sarili nito), may mga bagong variable na nalilikha na nag-iimbak ng data para sa pamamaraang ito. Walang mga nakabahaging variable."

"Sa bawat tawag, isa pang kopya ng mga argumento ng pamamaraan, na may mga bagong halaga, ay nilikha sa memorya. Kapag bumalik tayo sa lumang pamamaraan, ang mga variable nito ay ginagamit doon. Sa madaling salita, sa panahon ng recursion aktwal na tinatawag natin ang ibang pamamaraan, ngunit kasama ang parehong code sa amin! "

"Nakikita ko. At paano gumagana ang pag-alis sa mga ganitong pamamaraan? Siguro isang halimbawa?"

"OK. Ang isang halimbawa ay nagkakahalaga ng isang libong salita. "Narito ang iyong halimbawa:"

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. I think I understand. Why do we need recursion?"

"Maraming, maraming mga gawain na maaaring hatiin sa magkakahiwalay na mga subtask na kapareho ng orihinal na gawain. Halimbawa, kailangan mong dumaan sa lahat ng mga elemento ng isang XML tree. Ang bawat elemento ay maaaring magkaroon ng ilang mga elemento ng bata, at mayroon silang kanilang mga elemento ng sariling anak."

"O kailangan mong ipakita ang listahan ng mga file na nasa isang direktoryo at lahat ng mga subdirectory nito. Kaya sumulat ka ng isang paraan na nagpapakita ng mga file ng kasalukuyang direktoryo. Pagkatapos ay upang makuha ang mga file ng lahat ng mga subdirectory, tatawagan mo ang iyong pamamaraan gamit ang isang ibang argumento: isang subdirectory."

"Halimbawa:"

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

"Linya 8 - Nakukuha namin ang listahan ng lahat ng mga file (at mga direktoryo) sa direktoryo ng dir."

"Mga Linya 10-11 - Kung ang file ay talagang isang direktoryo, pagkatapos ay tatawagan namin muli ang printAllFiles , ngunit sa pagkakataong ito ay may isa pang argumento: ang subdirectory."

"Line 13 - Ipinapakita namin ang pangalan ng kasalukuyang file."

"OK. I think I understand. Thank you, Bilaabo."