Recursion

"Hi, Amigo. Today Bilaabo will tell you about recursion."

As you know, in Java some methods call other methods. Additionally, when a method is called, specific arguments are passed to it, but the method's local variables take certain values while it runs.

"Uh-huh."

"And as you know, different methods' internal variables are independent of one another."

"Uh-huh."

"So imagine the situation where a method calls itself. This is called recursion. For example:"

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!

"I can see that the method calls itself in the code, but I honestly don't understand what's happening."

"Well, about the same thing that happens when a different method is called."

"No, I'm asking about what happens with the variables? With their values? And how do we exit the method? Or do we exit everything all at once?"

"Goodness gracious. It's all much simpler. Imagine that the method that calls itself has been multiplied many times. Then we would have the analogous situation:"

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!

"In other words, each time a method is called (even by itself), new variables are created that store the data for this method. There are no shared variables."

"With each call, another copy of the method arguments, with new values, is created in memory. When we return to the old method, its variables are used there. In other words, during recursion we actually call another method, but with the same code as ours!"

"I see. And how does exiting such methods work? Maybe an example?"

"OK. An example is worth a thousand words. "Here's your example:"

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?"

"There are many, many tasks that can be divided into separate subtasks that are identical to the original task. For example, you need to walk through all the elements of an XML tree. Each element can have several child elements, and they have their own child elements."

"Or you need to display the list of files that are in a directory and all its subdirectories. So you write a method that displays the files of the current directory. Then to get the files of all the subdirectories, you call your method using a different argument: a subdirectory."

"For example:"

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

"Line 8 – We get the list of all files (and directories) in the dir directory."

"Lines 10-11 – If the file is actually a directory, then we call printAllFiles again, but this time with another argument: the subdirectory."

"Line 13 – We display the name of the current file."

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