đệ quy

"Xin chào, Amigo. Hôm nay Bilaabo sẽ cho bạn biết về đệ quy."

Như bạn đã biết, trong Java, một số phương thức gọi các phương thức khác. Ngoài ra, khi một phương thức được gọi, các đối số cụ thể sẽ được truyền cho phương thức đó, nhưng các biến cục bộ của phương thức sẽ nhận các giá trị nhất định trong khi phương thức chạy.

"Uh-huh."

"Và như bạn đã biết, các biến nội bộ của các phương thức khác nhau độc lập với nhau."

"Uh-huh."

"Vì vậy, hãy tưởng tượng tình huống mà một phương thức gọi chính nó. Điều này được gọi là đệ quy. Ví dụ:"

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!

"Tôi có thể thấy rằng phương thức này tự gọi nó trong mã, nhưng tôi thực sự không hiểu chuyện gì đang xảy ra."

"Chà, về điều tương tự xảy ra khi một phương thức khác được gọi."

"Không, tôi đang hỏi về điều gì sẽ xảy ra với các biến? Với các giá trị của chúng? Và làm thế nào để chúng ta thoát khỏi phương thức? Hay chúng ta thoát tất cả mọi thứ cùng một lúc?"

"Trời đất ơi. Tất cả đơn giản hơn nhiều. Hãy tưởng tượng rằng phương thức gọi chính nó đã được nhân lên nhiều lần. Sau đó, chúng ta sẽ có tình huống tương tự:"

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!

"Nói cách khác, mỗi khi một phương thức được gọi (thậm chí bởi chính nó), các biến mới được tạo để lưu trữ dữ liệu cho phương thức này. Không có biến dùng chung."

"Với mỗi lệnh gọi, một bản sao khác của các đối số phương thức, với các giá trị mới, được tạo trong bộ nhớ. Khi chúng ta quay lại phương thức cũ, các biến của nó được sử dụng ở đó. Nói cách khác, trong quá trình đệ quy, chúng ta thực sự gọi một phương thức khác, nhưng với cùng mã với chúng ta! "

"Tôi hiểu rồi. Và làm thế nào để thoát khỏi những phương pháp như vậy? Có thể là một ví dụ?"

"OK. Một ví dụ đáng giá ngàn lời nói. "Đây là ví dụ của bạn:"

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. Tôi nghĩ tôi hiểu. Tại sao chúng ta cần đệ quy?"

"Có rất nhiều nhiệm vụ có thể được chia thành các nhiệm vụ con riêng biệt giống với nhiệm vụ ban đầu. Ví dụ: bạn cần duyệt qua tất cả các phần tử của một cây XML. Mỗi phần tử có thể có một số phần tử con và chúng có các phần tử con riêng."

"Hoặc bạn cần hiển thị danh sách các tệp trong một thư mục và tất cả các thư mục con của nó. Vì vậy, bạn viết một phương thức hiển thị các tệp của thư mục hiện tại. Sau đó, để lấy các tệp của tất cả các thư mục con, bạn gọi phương thức của mình bằng lệnh đối số khác nhau: một thư mục con."

"Ví dụ:"

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

"Dòng 8 – Chúng tôi lấy danh sách tất cả các tệp (và thư mục) trong thư mục dir."

"Dòng 10-11 – Nếu tệp thực sự là một thư mục, thì chúng tôi gọi lại printAllFiles , nhưng lần này với một đối số khác: thư mục con."

"Dòng 13 – Chúng tôi hiển thị tên của tệp hiện tại."

"OK. Tôi nghĩ là tôi hiểu rồi. Cảm ơn, Bilaabo."