Recursion & Backtracking

1. Recursion (Đệ quy) là gì?

Đệ quy đơn giản là một hàm gọi lại chính nó. Mọi hàm đệ quy chuẩn phải có 2 phần:

1. Base Case (Điểm dừng): Điều kiện để hàm dừng gọi lại chính nó (nếu không sẽ bị Stack Overflow).
2. Recursive Step (Bước đệ quy): Gọi lại hàm với input nhỏ hơn/đơn giản hơn.

function factorial(n: number): number {
    // 1. Base Case
    if (n === 1) return 1;
    
    // 2. Recursive Step
    return n * factorial(n - 1);
}

Call Stack (Ngăn xếp cuộc gọi)

Khi hàm A gọi B, A chưa xong, nó phải đợi B. Máy tính lưu trạng thái của A vào Stack. Nếu đệ quy quá sâu ($10,000+$), Stack sẽ đầy -> Maximum call stack size exceeded.

2. Backtracking (Quay lui)

Backtracking là thuật toán tìm kiếm giải pháp theo kiểu "thử và sai" (trial and error). Quy trình:

1. Choose: Chọn một lựa chọn.
2. Explore: Tiếp tục đi sâu (đệ quy) với lựa chọn đó.
3. Un-choose: Nếu đi vào ngõ cụt, quay lại (Backtrack) và bỏ chọn để thử hướng khác.

Ví dụ: Sinh tất cả các hoán vị (Permutations)

Cho nums = [1, 2, 3]. Tìm tất cả các cách sắp xếp.

function permute(nums: number[]): number[][] {
    const res: number[][] = [];
    
    function backtrack(path: number[]) {
        // Base Case: Nếu đường đi đã đủ độ dài
        if (path.length === nums.length) {
            res.push([...path]); // Lưu bản sao
            return;
        }

        for (const num of nums) {
            // Nếu số này đã dùng trong path hiện tại thì bỏ qua
            if (path.includes(num)) continue;

            // 1. Choose
            path.push(num);
            
            // 2. Explore
            backtrack(path);
            
            // 3. Un-choose (Backtrack)
            path.pop();
        }
    }

    backtrack([]);
    return res;
}

Trực quan hóa:

• Bắt đầu: []
• Chọn 1: [1]
  • Chọn 2: [1, 2]
    • Chọn 3: [1, 2, 3] -> Ghi nhận. Backtrack.
  • [1, 2] (pop 3). Pop 2.
  • Chọn 3: [1, 3]...

Ứng Dụng Thực Tế

• Routing: Tìm đường đi trong mê cung, hoặc Google Maps.
• Decision Trees: AI chơi cờ vua (thử đi một nước, tính toán, nếu xấu thì quay lại).
• UI Components: Render folder tree (thư mục lồng nhau), Comments lồng nhau.