Thực hành đệ quy: base case, trace và memo
Biến đệ quy từ nỗi sợ thành công cụ qua điều kiện dừng, truy vết ngăn xếp lời gọi và kỹ thuật ghi nhớ.
DễThuật toán ~45 phút
Ôn lại trước khi học
Giới thiệu
Bài này biến đệ quy thành công cụ quen tay. Bạn học điều kiện dừng và ghi nhớ.
Kiến thức cần nhớ
Hai mảnh của hàm đệ quy
- Điều kiện dừng cho đáp án ngay, không gọi tiếp.
- Bước đệ quy thu nhỏ bài toán rồi tự gọi.
- Thiếu dừng thì gọi mãi không dứt.
- Ví dụ đời thường: búp bê Nga, con trong nhỏ hơn con ngoài.
- Thu nhỏ sai thì không bao giờ tới điểm dừng.
Truy vết ngăn xếp lời gọi
- Mỗi lần tự gọi là chồng thêm 1 khung.
- Gặp dừng thì gỡ từng khung từ trên xuống.
- Thứ tự gỡ ngược thứ tự gọi, đúng LIFO.
- Ví dụ đời thường: chồng bát, đặt lên rồi lấy xuống.
Memo — ghi nhớ để khỏi tính lại
- Tính xong thì cất kết quả vào bảng.
- Gặp lại tham số cũ thì lấy ra dùng.
- Chỉ hiệu quả khi bài toán con lặp lại.
- Ví dụ đời thường: ghi đáp án ra giấy nháp.
memo = {} # bảng ghi nhớ
def f(n):
if n <= 1: # điều kiện dừng
return n
if n in memo: # có rồi thì dùng lại
return memo[n]
memo[n] = f(n-1) + f(n-2) # tính rồi cất
return memo[n]
Ví dụ
- Input: tính số hạng 5 của dãy truy hồi có memo. Output: mỗi chỉ số tính 1 lần.
- Giải thích: bảng nhớ cắt hết tính toán trùng lặp.
💻 Bài tập
Ngôn ngữ: C++ (hoặc Python cho bài đo). Nộp vào day-008/. Mọi hàm phải đệ quy, ghi rõ base case bằng comment.
Bài 1: Năm hàm đệ quy cơ bản
| Hàm | Mô tả | Test |
|---|---|---|
long long power(long long a, int n) | bằng chia đôi số mũ, | power(2,10)=1024, power(3,0)=1 |
int sumDigits(long long n) | Tổng chữ số, n >= 0 | sumDigits(9045)=18 |
bool isPalindrome(const std::string &s, int l, int r) | Chuỗi đối xứng | "racecar" true, "ab" false, "" true |
int countLeaves(const Node *root) | Đếm lá cây nhị phân | Cây ngày 7 có 4 lá |
void hanoi(int n, char from, char to, char via, std::vector<std::string> &moves) | Ghi từng bước chuyển đĩa | n=3 cho đúng 7 bước |
Bài 2: Vết stack
Thêm tham số depth vào hanoi và countLeaves. In mỗi lần vào hàm và ra hàm, thụt lề theo depth:
-> countLeaves(10)
-> countLeaves(5)
-> countLeaves(3)
<- 1
...
<- 4
Chụp output cho cây 7 nút vào README.md. Đánh dấu độ sâu stack lớn nhất.
Bài 3: Fibonacci ba cách (nâng cao)
Viết 3 hàm và đếm số lời gọi bằng biến toàn cục:
| Hàm | Kỳ vọng |
|---|---|
fibNaive(n) | Số lời gọi tăng theo hàm mũ |
fibMemo(n, memo) | Mỗi n tính 1 lần, |
fibIter(n) | Không đệ quy, bộ nhớ |
In bảng với n = 10, 20, 30, 40:
n fib(n) calls_naive calls_memo
10 55 177 19
20 6765 21891 39
30 832040 ... ...
Thêm: duyệt DFS đồ thị có chu trình 0-1, 1-2, 2-0, 2-3 bằng đệ quy. Viết bản có tập visited. Giải thích (không cần chạy) vì sao bản thiếu visited không dừng.
✅ Tiêu chí hoàn thành
- Mọi test mẫu pass.
- Mỗi hàm có comment chỉ rõ base case và bước thu nhỏ.
- Bảng số lời gọi Bài 3 khớp số thật đo được.
- Vẽ được cây lời gọi
fibNaive(5)và chỉ ra các nút bị tính lặp.
❓ Câu hỏi ôn tập
- Điều kiện dừng là gì?
- Truy vết ngăn xếp làm thế nào?
- Memo giúp gì, khi nào dùng?
- Quên tập đã thăm trên đồ thị vòng thì sao?
🌕 Bạn đã hoàn thành ngày 8. Làm hết bài tập phía trên rồi sang ngày tiếp theo.