Đệ quy ↔ lặp; khử đệ quy
Mọi thuật toán đệ quy đều viết lại được bằng vòng lặp (và ngược lại). Bài này dạy cách chuyển qua lại, và quan trọng hơn — khi nào nên dùng cái nào.
1. Cùng một bài, hai cách viết
Tính giai thừa n!:
Cùng kết quả. Bản đệ quy đọc gần với định nghĩa toán học hơn; bản lặp thì không tốn call stack (O(1) bộ nhớ thay vì O(n)).
2. Quy tắc chuyển đệ quy → lặp
Với đệ quy đơn giản (mỗi lần gọi chính mình một lần — gọi là đệ quy đuôi/tuyến tính):
1. Tạo một biến tích luỹ kết quả (thay cho giá trị trả về).
2. Dùng vòng lặp chạy theo cùng hướng đệ quy đi (vd n giảm 1 → for/while).
3. Cập nhật biến tích luỹ mỗi vòng (thay cho phép ghép khi quay ngược).
Ví dụ tổng 1 + 2 + ... + n:
3. Khi nào dùng cái nào?
| Dùng ĐỆ QUY khi | Dùng VÒNG LẶP khi |
|---|---|
| Bài toán tự nhiên đệ quy: cây, đồ thị, chia để trị | Lặp tuyến tính đơn giản (tổng, đếm, duyệt mảng) |
| Code rõ ràng hơn, gần định nghĩa | Cần tiết kiệm bộ nhớ (tránh O(n) call stack) |
| Độ sâu nhỏ, an toàn | Độ sâu lớn (triệu tầng) → tránh tràn stack |
Nguyên tắc: ưu tiên cái nào rõ ràng hơn cho bài toán đó. Đổi sang lặp khi lo tràn stack hoặc cần hiệu năng bộ nhớ.
4. Cảnh báo: đệ quy ngây thơ có thể CỰC chậm
Không phải đệ quy nào cũng "đẹp". Tính Fibonacci kiểu ngây thơ gọi lại trùng lặp khủng khiếp:
fib gọi chính nó hai lần mỗi tầng → cây gọi bùng nổ ~O(2ⁿ). Đây không phải lỗi của "đệ quy"
mà của tính lại trùng lặp — quy hoạch động (học sau) sẽ sửa bằng cách nhớ kết quả đã tính.
5. Mẫu nhận diện
- Đệ quy gọi mình một lần mỗi tầng → đổi sang vòng lặp dễ, nên đổi nếu lo bộ nhớ.
- Đệ quy gọi mình nhiều lần (cây) → coi chừng tính lại trùng lặp → nghĩ tới ghi nhớ (memo).
- Bài về cây/đồ thị/chia để trị → đệ quy thường tự nhiên hơn vòng lặp.
6. 🎮 Trò chơi: Đệ quy hay vòng lặp?
7. Quiz kiểm tra nhanh
8. Hoàn thành
…☑️ Ti ếp theo: 1.3.4 — Chia để trị (đệ quy chia đôi bài toán).