Chuyển tới nội dung chính

Đệ quy: base case & recursive case

Bạn sẽ học được gì

Đệ quy là khi một hàm tự gọi chính nó để giải bài toán nhỏ hơn. Bạn sẽ hiểu hai phần bắt buộc — base case (điều kiện dừng) và recursive case (bước thu nhỏ) — và thấy chúng hoạt động qua một ví dụ chạy từng tầng.

1. Trực quan: búp bê Nga (matryoshka)​

Mở một con búp bê Nga, bên trong là con nhỏ hơn, lại mở ra con nhỏ hơn nữa... tới con bé nhất không mở được thì dừng. Đệ quy y hệt: mỗi bước giải một bài nhỏ hơn, tới khi gặp bài nhỏ nhất giải được ngay thì dừng lại.

giai_thua(3)
   └─ cần 3 × giai_thua(2)
            └─ cần 2 × giai_thua(1)
                     └─ cần 1 × giai_thua(0)
                              └─ = 1   ← con búp bê bé nhất (BASE CASE)

2. Hai phần BẮT BUỘC của mọi hàm đệ quy​

  1. Base case (điều kiện dừng): trường hợp nhỏ nhất, trả lời được ngay không cần gọi tiếp. Đây là cái chặn đệ quy chạy mãi.
  2. Recursive case (bước đệ quy): tự gọi chính mình với đầu vào nhỏ hơn, tiến về phía base case.
def giai_thua(n):
    if n == 0:          # BASE CASE: dừng
        return 1
    return n * giai_thua(n - 1)   # RECURSIVE CASE: nhỏ dần về 0
Thiếu base case = thảm hoạ

Quên base case (hoặc bước đệ quy không tiến về base) → hàm gọi mãi không dừng → tràn ngăn xếp (stack overflow), chương trình sập. Học kỹ ở bài 1.3.2.

3. Chạy debug: đi xuống rồi quay ngược​

Đệ quy có hai pha: đi xuống (gọi sâu dần tới base case) rồi quay ngược (trả kết quả lên). Bước qua giai_thua(3) và để ý hai pha đó:

🐞 giai_thua(3) — đi xuống rồi quay ngượcBước 1/13
1def giai_thua(n):
2  if n == 0:
3      return 1
4  return n * giai_thua(n - 1)
Biến tại bước này
n3
👉 Gọi giai_thua(3). PHA ĐI XUỐNG bắt đầu.

4. Code mẫu (chạy thật)​

Đang tải trình chạy code…

Thử đổi giai_thua(5) thành số khác và chạy lại. Lưu ý: cả hai hàm đều có base case (n == 0) và recursive case (gọi với n - 1, nhỏ dần về 0).

5. Cách NGHĨ đệ quy (đừng cố lần theo từng tầng)​

Người mới hay cố "chạy trong đầu" hết mọi tầng — rất rối. Mẹo: tin tưởng. Giả sử giai_thua(n - 1) đã đúng, thì n × giai_thua(n - 1) có đúng không? Nếu có, và base case đúng, thì cả hàm đúng. Chỉ cần kiểm 2 điều:

  1. Base case có đúng không?
  2. Recursive case: giả sử bài nhỏ hơn đã giải đúng, ghép lại có ra bài lớn không?

6. Mẫu nhận diện​

  • Bài toán tự chứa bản nhỏ hơn của chính nó (giai thừa, tổng, duyệt cây, chia để trị).
  • Luôn hỏi: base case là gì? và mỗi lần gọi có nhỏ dần về base case không?

7. 🎮 Trò chơi: Đệ quy​

🎮 Hiểu đệ quyCâu 1/4· Điểm 0· 🔥 0

Nhớ: base case = điều kiện dừng; recursive case phải nhỏ dần về base case.

Một hàm đệ quy THIẾU base case sẽ?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Hai phần bắt buộc của một hàm đệ quy là?
2. Vai trò của base case là gì?
3. Trong giai_thua(n) = n * giai_thua(n-1), điều gì đảm bảo nó tiến về base case?

9. Hoàn thành​

…

☑️ Tiếp theo: 1.3.2 — Ngăn xếp lời gọi & tràn stack (đệ quy "tốn chỗ" ở đâu).