Login

Đệ quy là gì? Cách hiểu và viết hàm đệ quy không bị rối

  • author-image

    Nguyễn Đình Cường

  • blog-tag
  • blog-comment 0 comment
  • created-date 09 Nov, 2026
blog-thumbnail

Đệ quy làm nhiều người mới thấy choáng: một hàm lại tự gọi chính nó? Thực ra ý tưởng khá tự nhiên, giống như hai tấm gương đối diện nhau hay búp bê Nga lồng nhau. Chỉ cần nắm hai quy tắc, bạn sẽ viết được đệ quy đúng.

Đệ quy là gì?

Đệ quy (recursion) là kỹ thuật một hàm tự gọi lại chính nó để giải bài toán nhỏ hơn, cho đến khi gặp trường hợp đủ đơn giản để trả lời ngay. Mọi hàm đệ quy đúng đều có hai thành phần:

  1. Trường hợp cơ sở (base case): tình huống đơn giản nhất, trả kết quả mà không gọi tiếp.
  2. Bước đệ quy: gọi chính hàm với bài toán nhỏ hơn, tiến dần về trường hợp cơ sở.

Thiếu trường hợp cơ sở, hàm gọi mãi không dừng và chương trình báo lỗi tràn ngăn xếp (stack overflow).

Ví dụ kinh điển: giai thừa

Giai thừa của n là tích 1 x 2 x ... x n. Ta nhận thấy n! = n x (n-1)!, và 0! = 1.

def giai_thua(n):
    if n == 0:          # trường hợp cơ sở
        return 1
    return n * giai_thua(n - 1)   # bước đệ quy

print(giai_thua(5))   # 120

Khi gọi giai_thua(3), chuỗi diễn ra như sau: 3 * giai_thua(2) → 3 * (2 * giai_thua(1)) → 3 * (2 * (1 * giai_thua(0))) → 3 * 2 * 1 * 1 = 6. Mỗi lời gọi chờ lời gọi con trả về rồi mới tính tiếp.

Máy tính theo dõi các lời gọi thế nào?

Mỗi lần gọi hàm, hệ thống tạo một "khung" trên ngăn xếp lời gọi (call stack) chứa tham số và biến cục bộ. Với đệ quy, các khung chồng lên nhau cho đến khi chạm trường hợp cơ sở rồi được gỡ dần. Vì ngăn xếp có giới hạn (Python mặc định khoảng một nghìn tầng), đệ quy quá sâu sẽ gây lỗi RecursionError.

Ví dụ thứ hai: tổng các phần tử và đảo chuỗi

def tong(ds):
    if not ds:              # danh sách rỗng
        return 0
    return ds[0] + tong(ds[1:])

def dao_chuoi(s):
    if len(s) <= 1:
        return s
    return dao_chuoi(s[1:]) + s[0]

print(tong([1, 2, 3, 4]))   # 10
print(dao_chuoi("abc"))     # cba

Cả hai đều theo mẫu: xử lý một phần tử, giao phần còn lại cho chính hàm. Cách tư duy này gọi là "tin tưởng đệ quy": giả sử hàm đã đúng cho bài nhỏ hơn, bạn chỉ cần ghép kết quả.

Fibonacci và bài học về hiệu năng

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

Cách viết này đúng nhưng rất chậm với n lớn, vì tính đi tính lại cùng một giá trị nhiều lần. Có thể khắc phục bằng ghi nhớ kết quả (memoization):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))   # 12586269025

Đệ quy hay vòng lặp?

Mọi đệ quy đều viết lại được bằng vòng lặp (kèm stack nếu cần) và ngược lại. Hãy chọn đệ quy khi bài toán có cấu trúc tự lặp lại, như duyệt cây, thư mục lồng nhau, quay lui, chia để trị. Chọn vòng lặp khi bài toán đơn giản, độ sâu lớn hoặc cần hiệu năng tốt nhất.

Mẹo để không bị rối

  • Viết trường hợp cơ sở trước tiên.
  • Chắc chắn mỗi lời gọi đều tiến gần hơn đến trường hợp cơ sở.
  • Thử với đầu vào rất nhỏ (0, 1, 2) và vẽ cây lời gọi trên giấy.
  • Đừng cố hình dung toàn bộ chuỗi gọi trong đầu; hãy kiểm tra logic từng bước.

Ví dụ thực tế: liệt kê file trong thư mục lồng nhau

Cấu trúc thư mục chứa thư mục con là bài toán đệ quy điển hình. Dưới đây là cách mô phỏng với dữ liệu lồng nhau:

thu_muc = {
    "ten": "du_an",
    "con": [
        {"ten": "main.py", "con": []},
        {"ten": "docs", "con": [
            {"ten": "huong_dan.md", "con": []}
        ]},
    ],
}

def in_cay(nut, cap=0):
    print("  " * cap + nut["ten"])
    for c in nut["con"]:
        in_cay(c, cap + 1)

in_cay(thu_muc)

Trường hợp cơ sở ở đây ngầm ẩn: nút không có con thì vòng lặp không chạy và hàm tự kết thúc. Đây chính là cách thư viện duyệt thư mục hoạt động, ví dụ os.walk. Cùng khuôn mẫu này áp dụng cho cây DOM của HTML, menu nhiều cấp và bình luận lồng nhau.

Bài tập: viết hàm đệ quy tính tổng các chữ số của một số nguyên, hàm tính lũy thừa luy_thua(a, n) bằng cách chia đôi n để chạy nhanh hơn, và hàm sinh mọi hoán vị của một chuỗi ngắn.

Kết luận

Đệ quy là cách diễn đạt gọn gàng cho các bài toán có tính tự tương tự. Hãy luyện với giai thừa, tổng các chữ số, tìm kiếm nhị phân đệ quy, duyệt cây. Sau một thời gian bạn sẽ thấy nó thanh lịch hơn là đáng sợ.

Nếu cần một lộ trình rõ ràng thay vì tự mò mẫm, codebem.com có nhiều khóa học phù hợp cho người mới.

author_photo
Nguyễn Đình Cường

0 comment