Hướng Dẫn Hoàn Chỉnh về Đệ Quy và Quay Lùi

Mục Lục

1. Cơ Bản về Đệ Quy
2. Truyền Tham Số Theo Giá Trị So Với Theo Tham Chiếu
3. Đối Tượng Có Thể Thay Đổi và Không Thay Đổi
4. Khi Nào Cần Quay Lùi?
5. Phương Pháp Trạng Thái Không Thay Đổi (Không Cần Quay Lùi)
6. Phương Pháp Trạng Thái Có Thể Thay Đổi (Cần Quay Lùi)
7. Nguyên Tắc Chung
8. So Sánh Hai Phương Pháp
9. Ví Dụ: Bài Toán Tập Hợp
10. Điểm Nhấn Quan Trọng

Cơ Bản về Đệ Quy

Đệ Quy là một phương pháp lập trình trong đó một hàm gọi chính nó với một bài toán con nhỏ hơn cho đến khi đạt được một trường hợp cơ bản.

Mẫu chung:

void recurse(params) {
    if (base case) return;   // điều kiện dừng
    // công việc
    recurse(smaller problem);
}

Truyền Tham Số Theo Giá Trị So Với Theo Tham Chiếu

• Java:

  • Kiểu nguyên thủy (int, char, double) → truyền theo giá trị (một bản sao được truyền).
  • Đối tượng (ArrayList, HashMap) → tham chiếu được truyền (do đó thay đổi ảnh hưởng đến bản gốc).

• Python:

  • Mọi thứ đều là đối tượng.
  • Đối tượng có thể thay đổi (list, dict, set) → thay đổi vẫn tồn tại qua các cuộc gọi hàm.
  • Đối tượng không thể thay đổi (int, str, tuple) → tạo đối tượng mới thay vì sửa đổi.

Đối Tượng Có Thể Thay Đổi và Không Thay Đổi

• Có thể thay đổi: Có thể bị thay đổi sau khi tạo.
  Ví dụ: Python list, dict; Java ArrayList, HashMap.

• Không thể thay đổi: Không thể bị thay đổi sau khi tạo.
  Ví dụ: Python int, str, tuple; Java String, Integer.

⚡ Tại sao điều này quan trọng?
👉 Bởi vì quay lùi chỉ cần thiết khi đệ quy thay đổi một đối tượng có thể thay đổi.

Khi Nào Cần Quay Lùi?

👉 Hãy tự hỏi:
Tôi có đang thay đổi một cấu trúc dữ liệu chung không?

• ✅ Có (có thể thay đổi, như list/mảng) → Cần quay lùi
  • Mô hình: thêm → đệ quy → xóa
  • Đối tượng chung → cần hoàn tác.
• ❌ Không (không thể thay đổi, như chuỗi/số/bản sao mới) → Không cần quay lùi
  • Mỗi cuộc gọi đệ quy nhận một bản sao của riêng mình.
  • Không cần hoàn tác.

Phương Pháp Trạng Thái Không Thay Đổi (Không Cần Quay Lùi)

Mỗi cuộc gọi đệ quy nhận một bức ảnh mới của trạng thái.

• An toàn: không cần hoàn tác.
• Đánh đổi: sử dụng nhiều bộ nhớ hơn.

Ví Dụ (Các tổ hợp phím trên điện thoại, chuỗi không thể thay đổi)

def pad(p, up):
    if not up:
        print(p)
        return
    digit = int(up[0])
    mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    for ch in mapping[digit]:
        pad(p + ch, up[1:])   # tạo chuỗi mới mỗi lần gọi

Tại đây p + ch tạo một chuỗi mới mỗi lần → không cần hoàn tác.

Phương Pháp Trạng Thái Có Thể Thay Đổi (Cần Quay Lùi)

Các cuộc gọi đệ quy chia sẻ cùng một đối tượng.
Chúng ta phải hoàn tác các thay đổi sau đệ quy để tránh làm hỏng kết quả.

• Hiệu quả: sử dụng ít bộ nhớ hơn.
• Rủi ro: phải hoàn tác đúng cách.

Ví Dụ (Các tổ hợp phím trên điện thoại, danh sách có thể thay đổi)

def letter_combinations(digits):
    mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    ans = []
    def solve(index, path):
        if index == len(digits):
            ans.append("".join(path))
            return
        for ch in mapping[int(digits[index])]:
            path.append(ch)           # thêm
            solve(index+1, path)
            path.pop()                # hoàn tác (quay lùi)
    solve(0, [])
    return ans

Tại đây path là chung → sau khi khám phá một nhánh, chúng tôi pop() để thiết lập lại.

Nguyên Tắc Chung

• Nếu sử dụng trạng thái không thể thay đổi (chuỗi, int, tuple) → Không cần quay lùi.
• Nếu sử dụng trạng thái có thể thay đổi (list, mảng, dict, set) → Cần quay lùi.

So Sánh Hai Phương Pháp

Ví Dụ: Bài Toán Tập Hợp

Không Có Quay Lùi (bản sao danh sách không thay đổi)

def subsets(nums):
    ans = []
    def dfs(index, path):
        if index == len(nums):
            ans.append(path[:])   # sao chép (danh sách mới)
            return
        dfs(index+1, path + [nums[index]])   # danh sách mới được tạo
        dfs(index+1, path)                   # không thay đổi
    dfs(0, [])
    return ans

Có Quay Lùi (danh sách chung có thể thay đổi)

def subsets(nums):
    ans = []
    def dfs(index, path):
        if index == len(nums):
            ans.append(path[:])   # sao chép cuối cùng
            return
        path.append(nums[index])   # thêm
        dfs(index+1, path)
        path.pop()                 # hoàn tác
        dfs(index+1, path)
    dfs(0, [])
    return ans

Điểm Nhấn Quan Trọng

1. Đệ Quy = phân chia bài toán thành các bài toán con nhỏ hơn.
2. Quay Lùi = đệ quy + hoàn tác thay đổi.
3. Kiểm tra khả năng thay đổi:
   • Không thể thay đổi → không cần quay lùi.
   • Có thể thay đổi → cần quay lùi.
   1. Đánh đổi:
   • Không thể thay đổi → đơn giản hơn, nhiều bộ nhớ hơn.
   • Có thể thay đổi → hiệu quả hơn, cần hoàn tác cẩn thận.