Đệ quy (Recursion) và Quay lui (Backtracking) trong Python

Đệ quy (Recursion)

Đệ quy là kỹ thuật hàm gọi chính nó để giải quyết bài toán bằng cách chia nhỏ thành các bài toán con cùng cấu trúc. Mọi hàm đệ quy cần 2 thành phần:

• Base case (Trường hợp cơ sở): Điều kiện dừng, không gọi đệ quy nữa.
• Recursive case (Trường hợp đệ quy): Gọi lại hàm với input nhỏ hơn, tiến về base case.

Ví dụ: Tính giai thừa (Factorial)

def factorial(n):
    # Base case
    if n == 0:
        return 1
    # Recursive case
    return n * factorial(n - 1)

print(factorial(4))  # 24

Quá trình gọi: factorial(4) → 4 * factorial(3) → 4 * 3 * factorial(2) → ... → 4 * 3 * 2 * 1 * 1 = 24

Quay lui (Backtracking)

Backtracking là thuật toán tìm kiếm giải pháp bằng cách xây dựng dần giải pháp, và khi phát hiện nhánh hiện tại không thể dẫn đến giải pháp hợp lệ, nó quay lui (undo) để thử nhánh khác.

• Dùng cho: N-Queens, Sudoku, Subset sum, Permutation, Combination, Maze solving.
• Cơ chế: Thử → Kiểm tra → Nếu sai: Quay lui (backtrack) → Thử lựa chọn khác.

Ví dụ Backtracking: Hoán vị (Permutations)

def permute(nums):
    result = []
    
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i, num in enumerate(remaining):
            # Chọn
            path.append(num)
            # Đệ quy với phần còn lại
            backtrack(path, remaining[:i] + remaining[i+1:])
            # Bỏ chọn (Backtrack)
            path.pop()
    
    backtrack([], nums)
    return result

print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

So sánh

Lưu ý Python

• Giới hạn độ sâu đệ quy mặc định: 1000 (sys.getrecursionlimit()).
• Có thể tăng: sys.setrecursionlimit(2000) (cẩn thận stack overflow).
• Backtracking thường triển khai bằng đệ quy.