Đệ quy là gì: cách hoạt động, kèm ví dụ Python

Đệ quy giải quyết vấn đề gì

Một số bài toán được định nghĩa theo chính nó. Một thư mục chứa các tệp và các thư mục khác. Một nút cây có các cây con. Giai thừa của n bằng n nhân giai thừa của n − 1. Viết những bài toán này bằng vòng lặp thông thường thường cần một ngăn xếp tường minh chứa công việc đang chờ; đệ quy để ngôn ngữ giữ ngăn xếp đó giúp bạn.

Một hàm đệ quy có hai phần:

• Trường hợp cơ sở: đầu vào nhỏ nhất, trả lời trực tiếp. Với giai thừa, 0! = 1.
• Trường hợp đệ quy: thu nhỏ bài toán, gọi hàm trên phần nhỏ hơn và kết hợp kết quả. Với giai thừa, n! = n × (n − 1)!.

def factorial(n):
    if n == 0:                  # base case
        return 1
    return n * factorial(n - 1) # recursive case
print(factorial(5))   # 120

Ngăn xếp lời gọi, theo dõi từng bước

Mỗi lời gọi có một khung (frame) riêng trên ngăn xếp lời gọi, chứa bản sao n của riêng nó. Các lời gọi đi xuống cho đến trường hợp cơ sở, rồi kết quả quay ngược lên theo thứ tự đảo lại.

Độ sâu ngăn xếp ở đây là n + 1 khung, nên không gian phụ là O(n) dù không tạo list nào.

Đệ quy trên dữ liệu lồng nhau

Đệ quy hữu ích nhất khi hình dạng của dữ liệu tự nó mang tính đệ quy. Hàm này cộng tất cả các số trong một list có thể chứa các list khác ở độ sâu bất kỳ.

def deep_sum(items):
    total = 0
    for x in items:
        if isinstance(x, list):
            total += deep_sum(x)   # same problem, smaller piece
        else:
            total += x
    return total
print(deep_sum([1, [2, 3], [4, [5, [6]]]]))   # 21

Cùng mẫu này dùng để duyệt cây thư mục, tài liệu JSON, DOM của HTML hay cây nhị phân: xử lý nút hiện tại, rồi đệ quy vào từng nút con.

def power_set(items):
    if not items:
        return [[]]
    rest = power_set(items[1:])
    return rest + [[items[0]] + s for s in rest]
print(power_set([1, 2, 3]))
# [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Độ phức tạp của hàm đệ quy

Ước lượng chi phí bằng (số lời gọi) × (công việc mỗi lời gọi). Không gian tối thiểu bằng độ sâu ngăn xếp lớn nhất.

Các hệ thức truy hồi chia để trị như T(n) = 2T(n/2) + O(n) của sắp xếp trộn cho kết quả O(n log n). Hàm thực hiện hai lời gọi trên n − 1 sẽ tăng theo hàm mũ.

Memoization: ngừng lặp lại công việc

Hàm Fibonacci ngây thơ tính lại cùng các giá trị nhiều lần: fib(5) gọi fib(3) hai lần và fib(2) ba lần. Lưu kết quả vào bộ nhớ đệm ngay lần tính đầu tiên biến thời gian hàm mũ thành tuyến tính. functools.lru_cache của Python (hoặc functools.cache, Python 3.9+) làm việc này chỉ bằng một decorator.

from functools import lru_cache
def fib_slow(n):
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)
@lru_cache(maxsize=None)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)
print(fib_slow(20))   # 6765, about 22,000 calls
print(fib(90))        # 2880067194370816120, 91 distinct calls

Đệ quy có memoization là dạng từ trên xuống của quy hoạch động. Dạng từ dưới lên điền một bảng bằng vòng lặp.

Giới hạn đệ quy và chuyển sang vòng lặp

Bạn có thể nâng giới hạn bằng sys.setrecursionlimit(), nhưng đệ quy quá sâu vẫn có thể làm sập trình thông dịch. Với đầu vào có thể rất sâu, như danh sách liên kết một triệu nút hoặc cây suy biến, hãy viết lại hàm bằng vòng lặp và một ngăn xếp tường minh.

def deep_sum_iter(items):
    total, stack = 0, [items]
    while stack:
        current = stack.pop()
        for x in current:
            if isinstance(x, list):
                stack.append(x)
            else:
                total += x
    return total
print(deep_sum_iter([1, [2, 3], [4, [5, [6]]]]))   # 21

Lỗi thường gặp

• Thiếu trường hợp cơ sở hoặc không bao giờ đạt tới nó, ví dụ factorial(-1) với đoạn mã trên không bao giờ về 0 và kết thúc bằng RecursionError.
• Trường hợp đệ quy không thu nhỏ đầu vào, chẳng hạn gọi f(n) từ chính f(n).
• Quên return kết quả đệ quy: factorial(n - 1) không có return sẽ cho None.
• Sao chép dữ liệu ở mỗi lời gọi. items[1:] sao chép list, nên đệ quy trên các lát cắt của list dài tốn O(n²) thời gian; hãy truyền chỉ số thay vào đó.
• Dùng đối số mặc định có thể thay đổi như def f(x, seen=[]) để mang trạng thái giữa các lời gọi; cùng một list được chia sẻ cho mọi lời gọi hàm.

Khi nào nên dùng đệ quy

Dùng đệ quy khi dữ liệu hoặc bài toán vốn mang tính đệ quy: cây, đồ thị (tìm kiếm theo chiều sâu), cấu trúc lồng nhau, phân tích biểu thức, quay lui (hoán vị, N-Queens, sudoku) và chia để trị (sắp xếp trộn, sắp xếp nhanh, tìm kiếm nhị phân). Dùng vòng lặp khi bài toán chỉ là một dãy đơn giản, hoặc khi độ sâu có thể tăng theo kích thước đầu vào trong Python.

Trong phỏng vấn, câu hỏi về đệ quy thường kiểm tra việc bạn nêu được trường hợp cơ sở, trường hợp đệ quy, chi phí thời gian và không gian kể cả ngăn xếp, và khi nào memoization có ích.