Tính giai thừa bằng đệ quy trong Python
factorial(6) gọi factorial(5), rồi factorial(5) gọi factorial(4)... Xem đệ quy chồng lời gọi rồi rút dần về 720 như thế nào.
- Trường hợp cơ sở và trường hợp đệ quy
- Các lời gọi chồng lên và trả về ra sao
- Giới hạn đệ quy của Python
factorial(1)trường hợp cơ sởtrả về 1factorial(2)trả về 2 * 1 = 2factorial(3)trả về 3 * 2 = 6factorial(4)trả về 4 * 6 = 24
Mỗi lời gọi chờ một lời gọi nhỏ hơn
Vấn đề
Có những bài toán được mô tả tự nhiên qua một phiên bản nhỏ hơn của chính nó: thư mục chứa thư mục, cây gia phả chứa những cây gia phả nhỏ hơn, n! bằng n nhân (n - 1)!. Đệ quy (recursion) cho phép bạn viết code đi đúng theo những định nghĩa như vậy.
Hình dung đời thường
Đệ quy giống một hàng người chuyền nhau một câu hỏi. Muốn biết 6!, người đầu hàng hỏi người kế bên 5! bằng bao nhiêu rồi đứng chờ. Người đó lại hỏi tiếp 4!, cứ thế cho tới người được hỏi 1!, người này trả lời được ngay. Sau đó câu trả lời truyền ngược về đầu hàng, mỗi người nhân thêm con số của mình vào.
factorial(6)🙋 Người đầu hàng: 6 × câu trả lời đang chờnumber * factorial(number - 1)➡️ Hỏi người kế bên cùng câu hỏi, với số nhỏ hơnif number <= 1: return 1🛑 Người cuối hàng trả lời ngay: 1720⬅️ Câu trả lời truyền ngược về đầu hàng: 720Hàm đệ quy là hàm tự gọi chính nó với đầu vào nhỏ hơn cho tới khi gặp trường hợp cơ sở (base case) có thể trả lời ngay; ở đây factorial(n) = n × factorial(n - 1) và factorial(1) = 1.
Những điểm quan trọng
if number <= 1: return 1là trường hợp cơ sở; thiếu nó các lời gọi sẽ không bao giờ dừng.return number * factorial(number - 1)gọi lại chính hàm đó với số nhỏ hơn.factorial(6)chờfactorial(5),factorial(5)chờfactorial(4), cứ thế xuống tớifactorial(1).raise ValueError(...)từ chối số âm, vì với số âm hàm sẽ không bao giờ chạm tới trường hợp cơ sở.
Khi nào nên sử dụng?
- Bài toán định nghĩa qua phiên bản nhỏ hơn: cây, thư mục, dữ liệu lồng nhau.
- Thuật toán chia để trị như merge sort.
- Học cách ngăn xếp lời gọi hàm (call stack) hoạt động.
Khi nào chưa cần
- Việc lặp đơn giản như tính giai thừa trong code thật: vòng lặp hoặc
math.factorialnhanh hơn và không bị giới hạn độ sâu. - Đầu vào rất sâu: Python dừng ở khoảng 1.000 lời gọi lồng nhau với lỗi RecursionError.
Xem cách hoạt động
Nhấn Từng bước để theo từng lời gọi. Lời gọi mới được đẩy lên call stack, và mỗi lời gọi trả giá trị về cho nơi đã gọi nó.
Code ví dụ
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
Kết quả khi chạy
720
Giải thích code
Khi number bằng 0 hoặc 1, hàm trả về 1 ngay lập tức. Đây là điều kiện dừng giúp đệ quy không chạy mãi. Với các giá trị khác, hàm trả về number nhân với factorial(number - 1). Mỗi lần gọi đệ quy được lưu trên ngăn xếp (call stack), nên độ sâu đệ quy là O(n).
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Lỗi hay gặp
Quên trường hợp cơ sở
Hàm tự gọi mãi cho tới khi Python báo lỗi RecursionError.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
Bạn học xong bài này chưa?
Đánh dấu đã học để theo dõi tiến độ của bạn.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
- Giai thừa Nhân tất cả các số nguyên dương từ 1 đến n. Dễ
- Lũy Thừa Đệ Quy Tính lũy thừa bằng đệ quy bằng cách chia đôi số mũ. Trung bình