Đệ quy là gì: cách lập trình bằng cách gọi lại chính hàm
Đệ quy (recursion) là kỹ thuật lập trình trong đó một hàm tự gọi lại chính nó để giải quyết bài toán nhỏ hơn, lặp lại cho tới khi đạt được điều kiện dừng (base case). Kỹ thuật này đặc biệt hiệu quả cho các bài toán có cấu trúc phân rã tự nhiên: duyệt cây, quy hoạch động, chia để trị và backtracking.
Đệ quy xuất hiện xuyên suốt lịch sử lập trình máy tính, kể cả trong khái niệm lập trình hàm mà Alan Turing và Alonzo Church phát triển. Một cách nói kinh điển về sức mạnh của nó là: nếu một tác vụ chỉ gọi lại chính nó với các tham số nhỏ hơn, thì máy tính có thể tự giải quyết tác vụ đó mà không cần bất kỳ công thức nào khác.
Điều kiện cần có của một hàm đệ quy
Một hàm đệ quy đúng đắn luôn có hai phần không thể thiếu:
- Điều kiện dừng (base case) – trường hợp mà hàm trả về kết quả mà không gọi lại chính nó.
- Bước giảm (recursive step) – trường hợp gọi lại hàm với tham số nhỏ hơn, tiến dần về điều kiện dừng.
Thiếu điều kiện dừng sẽ dẫn tới vòng lặp vô hạn (infinite recursion) và làm tràn ngăn xếp lời gọi. Thiếu bước giảm thì hàm không bao giờ tiến tới điều kiện dừng. Đây là hai lỗi phổ biến nhất khi mới học đệ quy, và cả hai đều dễ phát hiện khi chạy thử chương trình.
Ví dụ kinh điển – tính giai thừa:
DE QUY:
GIAI THUA(n):
neu n <= 1: tra ve 1
tra ve n x GIAI THUA(n - 1)
LAP (tuong duong):
GIAI_THUA_ITER(n):
kq = 1
cho i tu 2 den n: kq = kq x i
tra ve kqCơ chế bên trong: ngăn xếp lời gọi (call stack)
Mỗi lần hàm đệ quy được gọi, hệ thống tạo một khung ngăn xếp mới (stack frame) chứa các biến cục bộ và địa chỉ trả về. Khi hàm kết thúc, khung đó bị giải phóng và điều khiển trở về khung bên dưới. Đó là lý do các hàm đệ quy viết bằng ngôn ngữ C (không có quản lý bộ nhớ tự động) dễ gặp lỗi stack overflow khi chiều sâu vượt quá kích thước ngăn xếp.
Python quản lý điều này bằng giới hạn đệ quy mặc định 1000. Vượt quá ngưỡng này sẽ sinh ra ngoại lệ RecursionError, vì lời gọi quá sâu có thể làm tràn ngăn xếp C bên dưới và gây crash toàn bộ interpreter. Hàm sys.setrecursionlimit() cho phép điều chỉnh ngưỡng này.
Quy trình mở khung và giải phóng khung diễn ra theo nguyên tắc vòng sau cùng vào trước ra (LIFO). Nhờ đó một bài toán đệ quy luôn phải chạy ngược lại từ điều kiện dừng về điểm xuất phát, và thứ tự hoàn thành các lời gọi chính là thứ tự ngăn xếp được giải phóng.
Đệ quy trực tiếp và đệ quy tương tác
Hai hàm gọi lẫn nhau trực tiếp tạo thành mutual recursion (đệ quy tương tác), dùng phổ biến khi phân tích biểu thức: isExpression() gọi isTerm() và ngược lại. Loại này không thể gom về một hàm duy nhất mà không làm mất tính tự nhiên của thuật phân tích.
Tháp Hà Nội (Tower of Hanoi) là ví dụ kinh điển cho đệ quy: với n đĩa, số bước tối thiểu là 2^n – 1. Với 3 đĩa cần 7 bước, với 10 đĩa là 1023 bước – tăng theo cấp số nhân. Bài toán này không có lời giải vòng lặp nào đơn giản bằng, minh hoạ rõ sức mạnh biểu đạt của đệ quy.
Lời giải đệ quy của Tháp Hà Nội dựa trên ba bước: chuyển n-1 đĩa sang cọc trung gian, chuyển đĩa lớn nhất sang cọc đích, rồi chuyển n-1 đĩa còn lại sang cọc đích. Cùng một khuôn mẫu gọi lại chính nó với n-1 đĩa, lặp lại cho tới khi n bằng 1.
Đệ quy đuôi (tail recursion)
Đệ quy đuôi là trường hợp lời gọi đệ quy là thao tác cuối cùng của hàm, nên kết quả của nó được trả thẳng về nơi gọi mà không cần chờ khung hàm hiện tại hoàn tất. Các ngôn ngữ như Scheme, Haskell hay OCaml tối ưu trường hợp này thành vòng lặp thật, nên đệ quy sâu không làm tràn ngăn xếp.
Python không thực hiện tối ưu đệ quy đuôi, nên vẫn phải dựa vào ngăn xếp lời gọi. Nếu gặp trường hợp đệ quy đuôi rất sâu, hãy viết lại thành vòng lặp hoặc dùng kỹ thuật trampoline.
Độ phức tạp và cây đệ quy
Naive recursive Fibonacci có độ phức tạp thời gian O(2^n) vì cây đệ quy tính lại nhiều giá trị trùng lặp. Có thể tối ưu bằng memoization (lưu kết quả đã tính) hoặc chuyển sang dynamic programming, đưa độ phức tạp xuống O(n). Đây chính là bài học phổ quát: đệ quy rõ ràng về mặt triết lý nhưng thường tốn bộ nhớ và thời gian hơn nếu không cẩn thận.
Master theorem là công cụ phân tích độ phức tạp cho các thuật toán chia để trị có dạng T(n) = aT(n/b) + O(n^c), cho biết kết quả là O(n^c log n) khi a = b^c, hay O(n^log_b a) khi a lớn hơn.
Khi nào nên dùng và khi nào nên tránh
| Nên dùng đệ quy | Nên tránh, dùng vòng lặp |
|---|---|
| Duyệt cây (thư mục, JSON, DOM) | Duyệt mảng tuyến tính |
| Chia để trị (quicksort, merge sort) | Tính giai thừa, tổng các số |
| Backtracking (sudoku, n-queens) | Xử lý chuỗi đơn giản |
| Xử lý file phân cấp (thư mục) | Vòng lặp vô tận hàng triệu lần |
Nguyên tắc thực hành: nếu bài toán có cấu trúc phân rã tự nhiên thành các bài toán con cùng dạng, hãy dùng đệ quy. Nếu đệ quy chỉ là cách viết vòng lặp một cách phức tạp hơn mà không mang lại lợi ích biểu đạt, hãy dùng vòng lặp – vừa dễ đọc vừa tránh rủi ro tràn ngăn xếp.
Trước khi viết một hàm đệ quy, hãy tự hỏi chiều sâu tối đa của nó là bao nhiêu. Nếu con số đó không xác định theo dữ liệu đầu vào, đệ quy là lựa chọn rủi ro vì một tập dữ liệu bất thường có thể làm tràn ngăn xếp mà không có dấu hiệu báo trước.
