🌳 Đệ quy và cây tìm kiếm

🎯 Mục tiêu bài học

1. Đặt vấn đề

Với mỗi đồ vật, ta có hai lựa chọn: không chọn hoặc chọn. Sau khi quyết định cho đồ vật hiện tại, phần còn lại vẫn là cùng một dạng bài toán nhưng nhỏ hơn.

1.1. Vì sao vòng lặp thường khó viết?

Nếu n = 3, ta có thể viết 3 vòng hoặc dùng bitmask. Nhưng khi n thay đổi, số vòng lặp cũng thay đổi. Đệ quy cho phép mô tả thống nhất: xử lý vị trí hiện tại rồi giao phần còn lại cho lời gọi sau.

1.2. Cây tìm kiếm xuất hiện như thế nào?

Ở vị trí i, ta rẽ thành hai nhánh. Mỗi nhánh lại tiếp tục rẽ ở vị trí i+1. Các nhánh này tạo thành một cây trạng thái.

2. Đệ quy cơ bản

if (n == 0) return 1;

return n * factorial(n - 1);

2.1. Mẫu suy nghĩ

1. Định nghĩa hàm đang giải bài toán gì.
2. Xác định trường hợp dừng.
3. Giả sử lời gọi nhỏ hơn đã đúng.
4. Ghép kết quả lời gọi nhỏ hơn để giải bài toán hiện tại.

3. Mô phỏng Call Stack với factorial

4. Cây đệ quy và cây tìm kiếm

5. Mô phỏng cây tìm kiếm: liệt kê tập con

6. Quay lui: chọn → gọi → bỏ chọn

Quay lui là mẫu đệ quy dùng để thử các lựa chọn. Sau khi thử một lựa chọn, ta phải hoàn tác để thử lựa chọn khác.

void backtrack(int i) {
    if (i == n) {
        print(current);
        return;
    }

    backtrack(i + 1);

    current.push_back(a[i]);
    backtrack(i + 1);
    current.pop_back();
}

for (int value = 1; value <= n; value++) {
    if (!used[value]) {
        used[value] = true;
        permutation.push_back(value);
        backtrack(position + 1);
        permutation.pop_back();
        used[value] = false;
    }
}

7. Phân tích thuật toán

8. Code mẫu

#include <bits/stdc++.h>
using namespace std;

long long factorial(int n) {
    if (n == 0) return 1;
    return 1LL * n * factorial(n - 1);
}

int main() {
    int n;
    cin >> n;
    cout << factorial(n);
}

#include <bits/stdc++.h>
using namespace std;

vector<int> a;
vector<int> current;

void generateSubsets(int index) {
    if (index == (int)a.size()) {
        for (int value : current) cout << value << ' ';
        cout << '\n';
        return;
    }

    generateSubsets(index + 1);

    current.push_back(a[index]);
    generateSubsets(index + 1);
    current.pop_back();
}

int main() {
    a = {1, 2, 3};
    generateSubsets(0);
}

int n;
vector<int> permutation;
vector<bool> used;

void backtrack(int position) {
    if (position == n) {
        for (int value : permutation) cout << value << ' ';
        cout << '\n';
        return;
    }

    for (int value = 1; value <= n; value++) {
        if (!used[value]) {
            used[value] = true;
            permutation.push_back(value);
            backtrack(position + 1);
            permutation.pop_back();
            used[value] = false;
        }
    }
}

vector<vector<int>> adj;
vector<bool> visited;

void dfs(int u) {
    visited[u] = true;
    cout << u << ' ';

    for (int v : adj[u]) {
        if (!visited[v]) dfs(v);
    }
}

def generate_subsets(a):
    current = []

    def backtrack(index):
        if index == len(a):
            print(current)
            return

        backtrack(index + 1)
        current.append(a[index])
        backtrack(index + 1)
        current.pop()

    backtrack(0)

9. Giải thích code

9.1. Vì sao factorial phải có n == 0?

Đó là điểm dừng. Nếu không có điểm dừng, hàm tiếp tục gọi factorial(n-1) mãi và làm tràn call stack.

9.2. Vì sao tập con có hai lời gọi?

Với mỗi phần tử, ta có đúng hai lựa chọn: không chọn hoặc chọn. Hai lựa chọn này tạo hai nhánh trong cây tìm kiếm.

9.3. Vì sao phải current.pop_back()?

Sau khi thử nhánh chọn phần tử, ta phải hoàn tác để trạng thái hiện tại trở về như trước khi thử nhánh đó.

9.4. Khi nào chuyển sang stack thủ công?

Khi độ sâu lớn, môi trường giới hạn stack, hoặc cần kiểm soát thứ tự xử lý trạng thái rõ hơn.

10. Lỗi thường gặp

• Quên base case.
• Recursive case không làm bài toán nhỏ hơn.
• Không return kết quả của lời gọi đệ quy.
• Quên hoàn tác trạng thái khi quay lui.
• Dùng đệ quy Fibonacci thô cho n lớn.
• Không ước lượng số trạng thái của cây tìm kiếm.
• Gọi đệ quy quá sâu gây stack overflow.
• DFS đồ thị nhưng không đánh dấu visited đúng thời điểm.

11. Quiz và bài tập