Một, Khái niệm về đệ quy là gì?

Đệ quy sử dụng cấu trúc điều kiện như if/switch. Ngược lại, các vòng lặp for, while, do-while hoạt động theo cơ chế lặp đi lặp lại.

Để hiểu rõ hơn, hãy xem xét bài toán sau: Làm thế nào để tính tổng từ 1 đến 100?

Nhiều người sẽ nghĩ ngay đến cách dùng vòng lặp for:

int tong = 0;
for (int i = 1; i <= 100; i++) {
    tong += i;
}
System.out.println(tong); // Kết quả: 5050

Một cách khác hiệu quả hơn là áp dụng công thức toán học:

int batDau = 1;
int ketThuc = 100;
int tong = (batDau + ketThuc) * ketThuc / 2;
System.out.println(tong); // Kết quả: 5050

Tuy nhiên, chúng ta cũng có thể giải quyết bài toán này bằng phương pháp đệ quy:

static int deQuy(int n) {
    if (n == 1) { // Điều kiện dừng của đệ quy
        return 1;
    } else {
        return n + deQuy(n - 1);
    }
}

Từ ví dụ trên, ta thấy rằng đệ quy có những ưu điểm và nhược điểm sau:

1. Ưu điểm: Khiến mã nguồn dễ đọc và hiểu hơn.
2. Nhược điểm: Sử dụng quá nhiều lần có thể gây ra lỗi StackOverflow hoặc làm chậm chương trình.

Lưu ý quan trọng: Mọi hàm đệ quy cần phải có một điều kiện dừng để tránh tạo thành vòng lặp vô tận.

Hai, Quá trình thực thi của đệ quy

Để hiểu rõ hơn cách hoạt động của đệ quy, hãy thử viết hàm tính giai thừa bằng cách tiếp cận đệ quy:

static int tinhGiaiThua(int n) {
    if (n == 0) { // Điều kiện dừng
        return 1;
    } else {
        return n * tinhGiaiThua(n - 1);
    }
}

Khi gọi tinhGiaiThua(5), chương trình sẽ lần lượt gọi tinhGiaiThua(4), tinhGiaiThua(3) cho đến khi đạt điều kiện dừng tại tinhGiaiThua(0). Sau đó, giá trị sẽ được trả ngược trở lại theo thứ tự ngược lại với các bước gọi.

Ba, Áp dụng vào trò chơi tháp Hà Nội

Luật chơi: Có ba cột A, B, C. Tất cả các đĩa được xếp chồng lên nhau theo thứ tự tăng dần kích thước trên cột A. Mục tiêu là di chuyển toàn bộ số đĩa từ cột A sang cột C, sử dụng cột B làm trung gian. Trong suốt quá trình, không được phép đặt đĩa lớn lên trên đĩa nhỏ.

Giả sử bạn cần di chuyển 3 đĩa từ cột A đến cột C:

1. Di chuyển 2 đĩa đầu tiên từ A đến B.
2. Di chuyển đĩa lớn nhất từ A đến C.
3. Di chuyển 2 đĩa từ B đến C.

Có thể rút ra quy luật chung như sau:

• Nếu chỉ có 1 đĩa, di chuyển trực tiếp từ nguồn đến đích.
• Nếu có nhiều hơn 1 đĩa:
• Trước tiên, di chuyển n-1 đĩa từ nguồn đến trung gian.
• Sau đó, di chuyển đĩa cuối cùng từ nguồn đến đích.
• Cuối cùng, di chuyển n-1 đĩa từ trung gian đến đích.

Dưới đây là đoạn mã Java để giải bài toán tháp Hà Nội:

static int soBuoc = 0;

public static void main(String[] args) {
    thapHaNoi(3, "A", "B", "C");
    System.out.println(soBuoc);
}

static void thapHaNoi(int n, String nguon, String trungGian, String dich) {
    if (n == 1) {
        System.out.println("Di chuyển từ " + nguon + " --> " + dich);
        soBuoc++;
    } else {
        thapHaNoi(n - 1, nguon, dich, trungGian); // Bước 1
        thapHaNoi(1, nguon, "", dich); // Bước 2
        thapHaNoi(n - 1, trungGian, nguon, dich); // Bước 3
    }
}

Bốn, Tổng kết

Đệ quy là công cụ mạnh mẽ giúp đơn giản hóa các bài toán phức tạp. Tuy nhiên, cần lưu ý đến giới hạn dung lượng stack và hiệu suất khi sử dụng.