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

Ngăn xếp lời gọi & tràn stack

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

Vì sao đệ quy "tốn chỗ", máy nhớ mình đang ở tầng nào bằng cách nào, và vì sao đệ quy quá sâu (hoặc thiếu base case) làm chương trình sập với lỗi tràn ngăn xếp.

1. Trực quan: chồng đĩa​

Mỗi lần gọi một hàm, máy đặt một "khung" (frame) lên trên cùng một chồng — gọi là ngăn xếp lời gọi (call stack). Khung chứa: hàm nào, biến cục bộ, đang chạy tới dòng nào. Khi hàm return, khung trên cùng bị lấy ra, máy quay lại khung dưới.

Giống chồng đĩa: đặt thêm đĩa lên trên (gọi hàm), lấy đĩa trên xuống (return). Vào sau ra trước.

2. Chạy debug: chồng khung lớn lên rồi xẹp xuống​

Bước qua dem_nguoc(3). Cột biến hiện ngăn xếp (đáy → đỉnh). Để ý nó cao dần khi gọi sâu, rồi xẹp khi return:

🐞 dem_nguoc(3) — call stack lớn lên rồi xẹpBước 1/9
1def dem_nguoc(n):
2  if n == 0:
3      return
4  print(n)
5  dem_nguoc(n - 1)
Biến tại bước này
stack[dem(3)]
👉 Gọi dem(3): đặt 1 khung lên chồng.

Đây cũng là lý do (nhắc ở bài 1.2.5) đệ quy tốn O(n) không gian dù không tạo mảng nào: mỗi tầng chiếm một khung.

3. Tràn ngăn xếp (stack overflow)​

Chồng khung có giới hạn. Nếu đệ quy quá sâu (hoặc vô hạn vì thiếu/sai base case), chồng vượt giới hạn → máy báo lỗi và sập. Bấm Run để thấy (Python giới hạn ~1000 tầng):

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

Hàm hong không có base case và còn đi xa dần base (n tăng) → gọi mãi → tràn. Python chặn lại bằng RecursionError thay vì để sập máy.

4. Ba nguyên nhân tràn stack thường gặp​

  1. Thiếu base case — không có điểm dừng.
  2. Base case không bao giờ tới — bước đệ quy đi sai hướng (vd n + 1 thay vì n - 1).
  3. Đệ quy quá sâu hợp lệ — bài thật sự cần đệ quy hàng triệu tầng → nên đổi sang vòng lặp (học ở bài 1.3.3).

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

  • Đệ quy mà chạy là sập / RecursionError → kiểm base case và hướng của bước đệ quy.
  • Đệ quy sâu theo n lớn → cẩn thận bộ nhớ call stack (O(n)); cân nhắc khử đệ quy.

6. 🎮 Trò chơi: Cái nào tràn stack?​

🎮 Cái nào tràn stack?Câu 1/4· Điểm 0· 🔥 0

Đệ quy chạy an toàn cần: có base case VÀ mỗi bước tiến VỀ base case.

Hàm này có an toàn không?

def f(n):
    if n == 0:
        return
    f(n + 1)

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Ngăn xếp lời gọi (call stack) lưu gì?
2. Tràn ngăn xếp (stack overflow) xảy ra khi?
3. Đệ quy tốn O(n) không gian vì?

8. Hoàn thành​

…

☑️ Tiếp theo: 1.3.3 — Đệ quy ↔ lặp; khử đệ quy.