Đệ quy: bài toán nhỏ hơn, điều kiện dừng và ngăn xếp lời gọi

🔁 Vì sao hàm đệ quy có thể chạy vô hạn?

Mỗi lời gọi phải đưa bài toán gần hơn tới điều kiện dừng. Nếu trạng thái không giảm theo một đại lượng hữu hạn hoặc nhánh nào đó bỏ qua base case, ngăn xếp lời gọi tiếp tục tăng cho tới lỗi.

Các lời gọi factorial 4, 3, 2, 1 xếp xuống ngăn xếp, gặp base case 1 rồi trả kết quả ngược lên — Đi xuống tạo lời gọi; đi lên kết hợp kết quả. Điều kiện dừng và bước tiến phải được chứng minh cùng nhau.

Ba phần của thiết kế

Base case: trường hợp giải trực tiếp, không gọi tiếp.
Recursive case: chuyển thành phiên bản nhỏ hơn cùng cấu trúc.
Progress measure: đại lượng giảm hoặc tiến tới biên hữu hạn sau mỗi bước.

Ví dụ factorial

fact(n)=1 nếu n≤1; ngược lại fact(n)=n·fact(n−1), với miền n nguyên không âm. Độ sâu ngăn xếp O(n), thời gian O(n).

⚠️ Đệ quy không tự động nhanh hơn

Fibonacci đệ quy ngây thơ tính lặp nhiều bài toán con và có thời gian tăng rất nhanh. Memoization hoặc vòng lặp có thể giảm chi phí; lựa chọn phụ thuộc cấu trúc và giới hạn hệ thống.

📚 Lý thuyết trọng tâm

Mục tiêu: Design recursive algorithms with a decreasing measure and base case, trace call stacks and compare recursive clarity with iterative resource use.. Khi học Đệ quy: bài toán nhỏ hơn, điều kiện dừng và ngăn xếp lời gọi, hãy xác định khái niệm, điều kiện áp dụng và mối liên hệ giữa các dữ kiện; không chỉ ghi nhớ kết luận.

🧭 Ví dụ có hướng dẫn

Chọn một tình huống điển hình của bài. Bước 1: ghi dữ kiện và câu hỏi cần giải quyết. Bước 2: chọn khái niệm hoặc quy tắc phù hợp. Bước 3: giải thích từng bước và kiểm tra kết quả với điều kiện ban đầu. Nếu đổi một dữ kiện, hãy dự đoán kết quả thay đổi thế nào.

✍️ Luyện tập

Tóm tắt bài bằng ba ý: khái niệm, điều kiện và kết luận.
Tự tạo một ví dụ đúng và một phản ví dụ; chỉ ra điểm quyết định.
Giải lại ví dụ khi thay đổi một dữ kiện, sau đó nêu cách kiểm chứng.

Checklist tự đánh giá

Tôi giải thích được “vì sao”, không chỉ nêu đáp án.
Tôi nhận ra trường hợp không áp dụng được quy tắc.
Tôi kiểm tra được đơn vị, bằng chứng hoặc tính hợp lí của kết luận.