Bài 30. Đệ quy (recursion)
Bài học này giới thiệu đệ quy (recursion) - kỹ thuật để một hàm tự gọi lại chính nó nhằm giải một bài toán nhỏ hơn, cùng dạng với bài toán ban đầu - cùng với phần không thể thiếu của mọi hàm đệ quy: điều kiện dừng (base case).
Bắt đầu bằng một hình dung
Hãy hình dung một bộ búp bê gỗ truyền thống của Nga, thường gọi là búp bê matryoshka: một con búp bê khoác áo hoa sặc sỡ, cao chừng hai bàn tay. Mở con búp bê ấy ra, bên trong lại hiện ra một con búp bê giống hệt về hình dáng và hoa văn, chỉ nhỏ hơn một chút. Mở tiếp con này, lại thấy một con nhỏ hơn nữa nằm bên trong - cứ như vậy, hết lớp này đến lớp khác, cho đến khi gặp một con búp bê đặc ruột, nhỏ nhất, không thể mở ra được nữa. Con búp bê nhỏ nhất ấy chính là điểm dừng của cả bộ: không phải vì có ai ra lệnh dừng lại, mà vì tự bản thân nó không còn gì để mở tiếp.
Nhiều bài toán trong lập trình cũng được giải theo đúng tinh thần của bộ búp bê đó: muốn giải một bài toán cỡ lớn, ta ‘mở’ nó ra và thấy bên trong một bài toán CÙNG DẠNG như vậy, chỉ nhỏ hơn - rồi lặp lại đúng cách làm đó cho bài toán nhỏ hơn, cho đến khi gặp một trường hợp nhỏ nhất, đơn giản đến mức giải được ngay, không cần mở thêm nữa. Cách giải một bài toán bằng cách quy bài toán đó về chính nó, ở quy mô nhỏ hơn, gọi là đệ quy.
Nội dung bài học
- Đệ quy là gì?
- Điều kiện dừng (base case) - phần bắt buộc phải có
- Khi nào nên dùng đệ quy?
Tóm tắt lý thuyết cần nhớ
- Đệ quy là khi một hàm tự gọi lại chính nó để giải một bài toán nhỏ hơn nhưng cùng dạng với bài toán ban đầu - bài toán cỡ
nđược giải dựa trên kết quả của bài toán cỡn - 1. - Mọi hàm đệ quy đều bắt buộc phải có điều kiện dừng (base case) - trường hợp nhỏ nhất, giải được ngay không cần gọi tiếp; thiếu điều kiện dừng sẽ khiến hàm gọi mãi không dừng, gây tràn ngăn xếp (
RecursionError). - Ví dụ kinh điển: tính giai thừa với
giai_thua(n) = n * giai_thua(n - 1), điều kiện dừng tạin = 0; hay tính tổng1 + 2 + ... + nvới điều kiện dừng tạin = 1. - Đệ quy giúp code ngắn gọn, tự nhiên với các bài toán chia nhỏ được thành bài toán cùng dạng; nhưng mỗi lượt tự gọi phải luôn tiến gần hơn về điều kiện dừng.
Thuật ngữ tiếng Anh trong bài
| Tiếng Anh | Đọc là | Nghĩa |
|---|---|---|
| recursion | ri-CƠ-sần | đệ quy Một hàm tự gọi lại chính nó để giải bài toán nhỏ hơn - giống búp bê Nga: mở ra lại thấy một búp bê giống vậy nhưng nhỏ hơn. |
| function | PHẮNG-sần | hàm Một 'cỗ máy nhỏ' lắp sẵn để làm một việc cụ thể. |
| return | ri-TƠN | lệnh trả về (return) Lệnh đưa kết quả từ trong hàm ra ngoài để dùng tiếp - như đưa món ăn nấu xong ra khỏi bếp để mang lên bàn. |
| base case | BÂY-x KÂY-x | điều kiện dừng Là trường hợp nhỏ nhất mà hàm đệ quy giải được ngay, không cần gọi lại chính nó nữa. |
| factorial | phác-TO-ri-ơl | giai thừa Là tích các số từ 1 tới n, viết là n!. |
Câu hỏi trắc nghiệm có đáp án
Mấy câu mẫu để bạn tự kiểm tra ngay. Trong ứng dụng, bài này có đủ 24 câu, chấm điểm tự động và giải thích từng câu sai.
- Một hàm tự gọi lại CHÍNH NÓ để giải một bài toán nhỏ hơn, cùng dạng với bài toán ban đầu
- Một hàm gọi một hàm KHÁC để thực hiện một công việc phụ trợ
- Một vòng lặp
forđược viết lồng bên trong một vòng lặpforkhác - Một biến được gán lại giá trị nhiều lần trong cùng một chương trình
- Là dòng lệnh dùng để in kết quả cuối cùng ra màn hình
- Là tham số đầu tiên được truyền vào hàm ở lượt gọi đầu tiên
- Là trường hợp nhỏ nhất, được giải quyết ngay mà không cần gọi lại hàm thêm lần nào nữa
- Là lượt gọi hàm được thực hiện nhiều lần nhất trong toàn bộ quá trình đệ quy
def giai_thua(n):
if n == 0:
return 1
else:
return n * giai_thua(n - 1)- 10
- 24
- 16
- Chương trình báo lỗi vì hàm thiếu điều kiện dừng
- a)Mọi hàm đệ quy đều bắt buộc phải có ít nhất một điều kiện dừng (base case).Đúng
- b)Nếu một hàm đệ quy thiếu điều kiện dừng, hàm đó sẽ tự dừng lại một cách an toàn ngay sau lượt tự gọi đầu tiên.Sai
- c)Trong hàm tong tính tổng 1 + 2 + ... + n ở bài học, điều kiện dừng ứng với trường hợp n = 1.Đúng
- d)Đệ quy là cách DUY NHẤT để giải các bài toán như tính tổng hay tính giai thừa; không thể dùng vòng lặp for hoặc while để thay thế.Sai
- (a) Đúng - thiếu điều kiện dừng, hàm sẽ tự gọi lại chính nó mãi, không bao giờ kết thúc.
- (b) Sai - nếu thiếu điều kiện dừng, hàm KHÔNG tự dừng an toàn, mà tiếp tục tự gọi lại chính nó cho đến khi tràn ngăn xếp và chương trình báo lỗi.
- (c) Đúng - đúng như hàm tong trong bài học, điều kiện dừng được đặt tại trường hợp n = 1, trả về 1 ngay lập tức.
- (d) Sai - mọi bài toán giải được bằng đệ quy đều có thể viết lại bằng vòng lặp for hoặc while, và ngược lại; đệ quy chỉ là một cách diễn đạt khác, không phải cách duy nhất.
Thử ngay: minh hoạ từng bước
Bấm từng bước để tự xem cơ chế hoạt động, hoặc bấm “Tự chạy” cho nó tiến mỗi giây một lần. Đổi được dữ liệu đầu vào - không cần đăng nhập.
Học trọn bài này trong ứng dụng
Bài giảng đầy đủ, 24 câu luyện tập chấm tự động, thi thử đúng cấu trúc đề tốt nghiệp (24 trắc nghiệm + 4 Đúng/Sai), bài thực hành máy tự chấm và gia sư AI giải thích chỗ sai.
Phần học miễn phí, không cần tạo tài khoản.
Bài liên quan - Lập trình, Thuật toán & CTDL (KHMT)
Cùng mạch kiến thức với bài này, học nối tiếp cho chắc phần lí thuyết.