Trong lập trình, đệ quy (recursion) đề cập đến quá trình hàm gọi chính nó trực tiếp hoặc gián tiếp. Đệ quy dùng giải quyết nhiều vấn đề trong khoa học máy tính.
Ngôn ngữ lập trình Java hỗ trợ tạo phương thức đệ quy, là phương thức gọi chính nó.
Trong hướng dẫn này, chúng ta sẽ thảo luận, kèm ví dụ, cách đệ quy hoạt động, và cách tạo hàm đệ quy trong Java. Sau khi đọc hướng dẫn này, bạn sẽ thành chuyên gia viết phương thức đệ quy trong Java.
Phương Thức Trong Java
Phương thức, đôi khi gọi là hàm, là khối mã thực hiện tác vụ cụ thể. Ví dụ, phương thức có thể dùng tính tổng mảng giá trị hoặc in nội dung mảng ra bảng điều khiển.
Cú pháp phương thức trong Java:
modifier static returnType methodName (Parameters) { // Method body }
Ví dụ, giả sử muốn tạo phương thức in câu Hôm nay là thứ Tư! Chúng ta đã qua nửa tuần! ra bảng điều khiển. Có thể làm bằng mã:
class Main { public static void printItsWednesday() { System.out.println("It's Wednesday! We're half-way through the week!"); } public static void main(String[] args) { printItsWednesday(); } }
Khi gọi phương thức bằng printItsWednesday(), kết quả sau trả về:
Hôm nay là thứ Tư! Chúng ta đã qua nửa tuần!
Nếu bạn quan tâm tìm hiểu thêm về phương thức Java, có thể đọc hướng dẫn đầy đủ về phương thức trong Java tại đây.
Trong ví dụ trên, gọi phương thức printItsWednesday() trong chương trình chính. Nhưng nếu gọi phương thức trong chính phương thức đó, chúng ta đã tạo phương thức đệ quy.
Đệ Quy Trong Java
Phương thức đệ quy là phương thức được gọi trong phương thức chính trước, sau đó được gọi trong chính phương thức đó. Cú pháp phương thức đệ quy:
static void executeMethod() { // Code here executeMethod(); // This is our recursive call // Code here } public static void main(String[] args) { executeMethod(); // This is the normal method call }
Khi chạy chương trình, phương thức executeMethod() được gọi trong chương trình chính. Điều này khiến mã trong phương thức executeMethod() chạy, trường hợp này bao gồm phương thức executeMethod(). Vì vậy, khi chương trình chạy, nó sẽ vào vòng lặp.
Chương trình tiếp tục thực thi phương thức executeMethod() cho đến khi điều kiện đáp ứng ngăn cản tiếp tục. Nếu không chỉ định điều kiện dừng đệ quy, chương trình chạy mãi mãi. Điều này gọi là đệ quy vô hạn (infinite recursion).
Tại sao nên dùng đệ quy? Thứ nhất, đệ quy có thể giảm độ phức tạp thời gian của chương trình trong một số trường hợp. Thứ hai, đệ quy có thể làm dễ dàng triển khai một số thuật toán theo cách dễ đọc và bảo trì hơn.
Dưới đây là vài ví dụ chương trình thường viết dùng đệ quy:
- Tính dãy Fibonacci
- Đảo ngược chuỗi
- Tính giai thừa của số
- Tính chiều cao cây nhị phân
Đó là vậy, đệ quy có thể chậm hơn viết phương thức tiêu chuẩn thực hiện tác vụ. Điều này vì đệ quy tạo vị trí lưu trữ mới cho biến mỗi lần phương thức đệ quy thực thi.
Ví Dụ Đệ Quy Trong Java
Hãy đi qua hai ví dụ minh họa cách đệ quy hoạt động trong Java.
Đảo Ngược Chuỗi Sử Dụng Đệ Quy
Giả sử xây dựng chương trình cho giáo viên trung học cơ sở đảo ngược chuỗi chứa điểm số học sinh trong năm. Chuỗi bắt đầu bằng điểm đầu tiên học sinh nhận được và kết thúc bằng điểm gần đây nhất. Chúng ta muốn đảo chuỗi để điểm gần đây nhất của học sinh đứng đầu chuỗi.
Có thể dùng mã sau đảo chuỗi:
public class ReverseGrades { public static String reverse(String grades) { if (grades.isEmpty()) return grades; return reverse(grades.substring(1)) + grades.charAt(0); } public static void main(String[] args) { String grades = "CBCBAABACAABA"; String reverse_grades = reverse(grades); System.out.println("This student's grades for the year are: " + reverse_grades); } }
Mã trả về:
Điểm năm học của học sinh này là: ABAACABAABCBC
Như bạn thấy, chương trình đã đảo nội dung chuỗi. Trong chương trình, tạo hàm đệ quy tên reverse().
Khi hàm reverse() thực thi, đầu tiên kiểm tra chuỗi grades có rỗng không. Nếu rỗng, trả về danh sách điểm về chương trình chính. Điều này dừng đệ quy vì lời gọi reverse() ở cuối hàm không có cơ hội chạy.
Nếu chuỗi grades không rỗng, chương trình thực thi phương thức reverse() lại và nối kết quả hàm với ký tự đầu tiên của câu. Dùng phương thức charAt() lấy ký tự đầu tiên câu, thêm vào bên trái phương thức reverse().
Sau khi chuỗi đảo ngược, thông báo This student’s grades for the year are: “, theo sau chuỗi đảo ngược điểm học sinh, trả về chương trình.
Tính Giai Thừa Sử Dụng Đệ Quy
Một trường hợp đệ quy hữu ích khác là tính giai thừa của số.
Trong toán học, giai thừa là tích của tất cả số nguyên dương nhỏ hơn hoặc bằng số nhân lại với nhau. Ví dụ, giai thừa của 5 bằng 5*4*3*2*1, tức 120. Vì phương thức giai thừa liên quan tính toán lặp lại, chúng là ví dụ thực tế tốt nơi đệ quy hữu ích giải quyết vấn đề.
Chương trình Java sau cho phép tính giai thừa của số 7 trong Java:
class Main { static int calculateFactorial(int number) { if (number != 0) return number * calculateFactorial(number-1); else return 1; } public static void main(String[] args) { int num = 7; int answer = calculateFactorial(num); System.out.println("The factorial of 7 is: " + answer); } }
Mã trả về:
The factorial of 7 is: 5040
Trong ví dụ này, tạo phương thức calculateFactorial() nhân số lưu trong tham số number với kết quả phương thức calculateFactorial() tiếp theo. Quá trình thực thi cho đến khi tham số number bằng 0.
Khi tham số number bằng 0, câu lệnh if trong mã trả về 1 và kết quả phương thức calculateFactorial() truyền về chương trình chính.
Vì vậy, phương thức calculateFactorial() thực hiện 7*6*5*4*3*2*1, sau đó trả lời về chương trình chính. Sau khi tính xong, thông báo The factorial of 7 is:, theo sau đáp án chương trình tính, in ra bảng điều khiển.
Kết Luận
Đệ quy là khái niệm lập trình mô tả phương thức gọi chính nó. Phương thức đệ quy hữu ích khi cần lặp lại tác vụ nhiều lần và dùng kết quả lần lặp trước trong lần lặp hiện tại.
Hướng dẫn này đi qua cơ bản đệ quy trong Java và cách tạo phương thức đệ quy. Ngoài ra, hướng dẫn đi qua hai ví dụ đệ quy trong thực tế, tham khảo đảo ngược chuỗi và tính giai thừa.
Bạn đã sẵn sàng bắt đầu làm việc với phương thức đệ quy trong Java như chuyên nghiệp!