Tổng quan
Đệ quy là kỹ thuật trong đó một hàm giải bài toán bằng cách tự gọi chính nó trên đầu vào nhỏ hơn, cho đến khi chạm trường hợp cơ sở có thể trả lời trực tiếp. Fibonacci ngây thơ — fib(n) = fib(n−1) + fib(n−2) — là minh họa kinh điển.
Mỗi lời gọi lại rẽ thành hai lời gọi nữa, nên đệ quy ngây thơ vẽ ra một cây gọi hàm phình theo cấp số nhân, tính đi tính lại cùng những bài toán con. Chính sự lãng phí đó là điều mà ghi nhớ (memoization) và quy hoạch động ra đời để khắc phục.
Đệ quy hoạt động thế nào?
- Định nghĩa trường hợp cơ sở: fib(0) = 0 và fib(1) = 1 trả về ngay lập tức.
- Với n lớn hơn, lời gọi sinh ra hai lời gọi con, fib(n−1) và fib(n−2).
- Đi xuống theo nhánh trái nhất của cây cho đến khi chạm một trường hợp cơ sở.
- Khi mỗi lời gọi trả về, giá trị của nó dồn ngược lên và cộng với anh em của mình cho đến khi gốc fib(n) được xác định.
Khi nào nên dùng?
- Các bài toán có cấu trúc tự tương tự — cây, dữ liệu lồng nhau, và chia để trị.
- Viết lời giải rõ ràng, khai báo, phản ánh trực tiếp một hệ thức truy hồi.
- Tránh đệ quy ngây thơ khi các bài toán con chồng lấn — thêm ghi nhớ hoặc chuyển sang lặp.
Phân tích độ phức tạp
Fibonacci ngây thơ thực hiện khoảng φ^n lời gọi (φ ≈ 1.618), nên thời gian chạy là O(φ^n) — theo cấp số nhân, gần O(2^n). Đệ quy còn dùng O(n) bộ nhớ ngăn xếp cho nhánh sâu nhất. Sự bùng nổ này hoàn toàn do tính lại các bài toán con chồng lấn.
Câu hỏi thường gặp
Vì sao Fibonacci đệ quy ngây thơ lại chậm đến vậy?
Vì nó tính lại cùng các bài toán con: fib(5) tính fib(3) hai lần, fib(2) ba lần, v.v., tạo ra số lời gọi theo cấp số nhân. Lưu lại kết quả giúp thu về thời gian tuyến tính.
Trường hợp cơ sở là gì và vì sao nó thiết yếu?
Trường hợp cơ sở là đầu vào nhỏ nhất được trả lời mà không đệ quy thêm. Thiếu nó, các lời gọi không bao giờ dừng, gây đệ quy vô hạn và tràn ngăn xếp.