Đệ quy trong Java

Đệ quy là một trong những cách giúp lập trình viên thực hiện dự án với code chặt chẽ và gọn gàng hơn. Trong bài viết này, chúng ta sẽ tìm hiểu thêm về đệ quy trong Java và một số ưu điểm nhược điểm của đệ quy với trình lặp trong Java.

Đệ quy là gì?

Đệ quy (Recursion) là một trong những giải thuật khá quen thuộc trong lập trình, mở rộng ra là trong toán học (thường được gọi với tên khác là “quy nạp”). Có một số bài toán, buộc phải sử dụng đệ quy mới giải quyết được, chẳng hạn như duyệt cây.

Một bài toán mang tính chất đệ quy khi nó có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa. Cứ tiếp tục như thế cho đến khi không thể chia nhỏ được được hoặc đạt được kết quả mong muốn.

Một hàm đệ quy bao gồm hai phần là phần cơ sở và phần đệ quy:

Phần cơ sở: Điều kiện thoát khỏi đệ quy. Hàm đệ quy không thể gọi mãi mà cần phải có một điểm dừng ( điểm neo) tại một trường hợp đặc biệt, được gọi là trường hợp suy biến.

Phần đệ quy: Thân hàm có chừa lời gọi đệ quy.

Điều kiện cơ sở trong đệ quy trong Java là gì?

Trong chương trình đệ quy, lời giải cho các trường hợp cơ sở được cung cấp và lời giải cho bài toán lớn hơn được thể hiện dưới dạng nhỏ hơn.

Ví dụ:

int fact(int n)

{

    if (n < = 1) // base case

        return 1;

    else    

        return n*fact(n-1);    

}Code language: JavaScript (javascript)

Trong ví dụ trên, trường hợp cơ sở cho n<=1 được xác định và giá trị lớn hơn của số có thể được giải quyết bằng cách chuyển đổi thành nhỏ hơn cho đến khi đạt được trường hợp cơ sở.

Làm thế nào một vấn đề được giải quyết bằng cách sử dụng đề quy

Ý tưởng là thể hiện một vấn đề dưới dạng một hoặc nhiều vấn đề nhỏ hơn và thêm một hoặc nhiều điều kiện cơ sở để dừng đệ quy. Ví dụ, chúng ta tính giai thừa n nếu chúng ta biết giai thừa của (n-1). Trường hợp cơ sở cho giai thừa sẽ là n=0. Chúng trả về kết quả là 1 khi n=0.

Ví dụ

public class RecursionExample {
    static int count = 0;
      
    static void welcome() {
        count++;
        if (count <= 5) { // Phần cơ sở: Điều kiện thoát khỏi đệ quy
            System.out.println(count + ". Welcome to gpcoder.com ");
            welcome(); // Phần đệ quy: Thân hàm có chứa lời gọi đệ quy
        }
    }
  
    public static void main(String[] args) {
        welcome();
    }
 
}Code language: JavaScript (javascript)

Ví dụ tính giai thừa

public class RecursionExample3 {
    static int factorial(int n) {
        if (n == 1)
            return 1;
        else
            return (n * factorial(n - 1));
    }
 
    public static void main(String[] args) {
        System.out.println("Giai thừa của 5 là: " + factorial(5));
    }
}Code language: JavaScript (javascript)

Output:

Giai thừa của 5 là: 120

Thiết kế giải thuật đệ quy

Thực hiện 3 bước sau:

• Tham số hóa bài toán
• Phân tích trường hợp chung: Đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tiến tới trường hợp suy biến
• Tìm trường hợp suy biến

Ưu và nhược điểm của đệ quy

Ưu điểm: một số trường hợp giúp code gọn ràng, dễ hiểu, giảm độ phức tạp, đặc biệt trong việc giải quyết các vấn đề dựa trên cấu trúc cây.

Nhược điểm: không tối ưu về mặt thời gian (so với sử dụng vòng lặp), gây tốn bộ nhớ.

Một số loại đệ quy

• Đệ quy tuyến tính (Linear Recursion): mỗi lần thực thi chỉ gọi đệ quy một lần. Xem ví dụ: Bài toán tính giai thừa, Dãy Fibonaci.
• Đệ quy nhị phân (Binary Recursion): mỗi lần thực thi có thể gọi đệ quy 2 lần. Xem ví dụ: Bài toán tháp Hà Nội, Tính tổ hợp chập K của N.
• Đệ quy lồng (Nested Recursion): tham số trong lời gọi đệ quy là một lời gọi đệ quy. Đệ quy lồng chiếm bộ nhớ rất nhanh. Xem ví dụ: Hàm số Ackermann.
• Đệ quy hỗ tương (Mutual Recursion): Các hàm gọi đệ quy lẫn nhau. Xem ví dụ: Xét tính chẵn lẻ của một số nguyên dương bằng đệ quy.
• Quay lui (Backtracking):
  • Trong lập trình, có một chiến lược giải bài toán một cách đầy đủ nhất, đảm bảo đủ mọi trường hợp bằng phương pháp Thử và Sai (Try and Error).
  • Nét đặc trưng của phương pháp này là ở chỗ các bước đi đến lời giải hoàn toàn bằng cách làm thử. Nếu có một lựa chọn được chấp nhận thì ghi nhớ các thông tin cần thiết các bước thử tiếp theo. Trái lại, nếu không có một lựa chọn nào thích hợp thì làm lại bước trước, xoá bớt các ghi nhớ và quay về chu trình thử với các lựa chọn còn lại. Hành động này được gọi là quay lui (Back tracking) và các giải thuật thể hiện phương pháp này gọi là các giải thuật quay lui.
  • Việc quay lui để thử tất cả các tổ hợp có thể có để đạt được lời giải cuối cùng.
  • Xem ví dụ Bài toán N-Hậu (N-Queen).

Tổng kết

Đệ quy trong Java là một yếu tố lập trình viên cần nắm rõ trong quá trình làm việc với các dự án Java. Hy vọng bài viết trên đã giúp bạn hiểu rõ hơn về đệ quy trong Java.