🔄 Đệ quy (Recursion)

Có hai cách để lặp lại một việc trong lập trình: vòng lặp (lặp từ dưới lên - bắt đầu từ bước nhỏ nhất, cộng dồn dần tới kết quả) và đệ quy (lặp từ trên xuống - một hàm tự gọi lại chính nó với một bài toán nhỏ hơn, cho tới khi chạm bài toán đủ nhỏ để giải trực tiếp). Đệ quy đặc biệt hợp với những bài toán mà “bài toán lớn được cấu thành từ chính nó, chỉ nhỏ hơn” - cây, đồ thị, chia để trị đều có hình dạng này.

Hai phần bắt buộc

Một hàm đệ quy luôn cần đúng hai phần: điều kiện dừng (base case) - trường hợp đủ nhỏ để trả lời ngay không cần gọi tiếp, và lời gọi đệ quy (recursive case) - thu nhỏ bài toán rồi gọi lại chính hàm đó.

def dem_nguoc(n):
    if n <= 0:           # base case: dừng khi chạm đáy
        print("Hết!")
        return
    print(n)
    dem_nguoc(n - 1)      # recursive case: gọi lại với bài toán nhỏ hơn

Chú ý

Thiếu base case, hoặc base case không bao giờ được chạm tới (ví dụ quên giảm n), hàm sẽ gọi chính nó vô hạn cho tới khi hết bộ nhớ dành cho lời gọi hàm - lỗi stack overflow. Đây là lỗi phổ biến nhất khi mới học đệ quy.

Vì sao đệ quy tốn bộ nhớ hơn vòng lặp

Mỗi lần một hàm gọi hàm khác (kể cả gọi chính nó), hệ thống cấp phát một khung nhớ (stack frame) để lưu biến cục bộ và vị trí cần quay về, đặt trên call stack. Khung này chỉ được giải phóng khi hàm đó return.

Với hàm tính giai thừa gọi đệ quy sâu n tầng trước khi tầng cuối cùng trả về:

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)   # còn "n *" đang chờ -> chưa return được

Gọi factorial(5) tạo ra chuỗi factorial(5) chờ factorial(4), chờ factorial(3)… cho tới factorial(1). Tại thời điểm sâu nhất, có 5 khung nhớ tồn tại đồng thời trên call stack - đây là lý do đệ quy thường tốn bộ nhớ O(n) trong khi vòng lặp tương đương chỉ cần O(1):

def factorial_loop(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res   # chỉ 1 khung nhớ duy nhất trong suốt quá trình

Mẹo

Có một trường hợp đặc biệt gọi là đệ quy đuôi (tail recursion): khi lời gọi đệ quy là thao tác cuối cùng trước khi hàm return (không còn phép tính nào chờ sau đó, như n * ở trên). Một số ngôn ngữ/trình biên dịch có thể tối ưu đệ quy đuôi để chỉ dùng O(1) bộ nhớ, tương đương vòng lặp. Tuy nhiên Python không hỗ trợ tối ưu này, nên viết đệ quy đuôi trong Python vẫn tốn O(n) bộ nhớ như đệ quy thường.

Bẫy kinh điển: Fibonacci tính đi tính lại

Fibonacci là ví dụ kinh điển cho thấy đệ quy có thể cực kỳ lãng phí nếu viết ẩu:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Nhìn qua tưởng đơn giản, nhưng fib(n-1) và fib(n-2) lại tiếp tục gọi fib(n-2), fib(n-3)… - cùng một giá trị fib(k) bị tính lại rất nhiều lần ở các nhánh khác nhau. Số lời gọi hàm tăng theo cấp O(2ⁿ) - với n = 40, chương trình có thể chạy hàng chục giây dù bài toán bản chất rất đơn giản.

Cách sửa: ghi nhớ (memoization) - lưu lại kết quả đã tính, tra lại thay vì tính lại:

def fib_memo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]   # O(n) thay vì O(2ⁿ)

Chỉ với một dict lưu lại kết quả trung gian, độ phức tạp giảm từ mũ xuống tuyến tính - đây chính là ý tưởng cốt lõi đằng sau quy hoạch động, được bàn kỹ ở trang Quy hoạch động.

Khi nào chọn đệ quy, khi nào chọn vòng lặp?

	Đệ quy	Vòng lặp
Code	Thường ngắn gọn, bám sát định nghĩa toán học của bài toán	Có thể dài hơn nhưng tường minh từng bước
Bộ nhớ	Tốn thêm O(depth) do call stack	O(1) nếu không cần cấu trúc phụ
Phù hợp nhất với	Cây, đồ thị, chia để trị, backtracking - nơi bài toán tự nhiên “chứa” phiên bản nhỏ hơn của chính nó	Bài toán lặp tuyến tính đơn giản, hoặc khi cần tối ưu bộ nhớ tối đa

Bất kỳ đệ quy nào cũng có thể viết lại thành vòng lặp bằng cách tự quản lý một stack thay cho call stack của hệ thống - nhưng code thường trở nên khó đọc hơn hẳn, nên chỉ nên làm khi thực sự cần tối ưu.