Thuật toán Python

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.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • 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(4)
  1. factorial(1)trường hợp cơ sởtrả về 1
  2. factorial(2)trả về 2 * 1 = 2
  3. factorial(3)trả về 3 * 2 = 6
  4. factorial(4)trả về 4 * 6 = 24
Lời gọi chồng dần từ dưới lên; kết quả trả về từ trên xuống.

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.

Từ một hàng người đến code
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ơn
if number <= 1: return 1🛑 Người cuối hàng trả lời ngay: 1
720⬅️ Câu trả lời truyền ngược về đầu hàng: 720
Mỗi lời gọi chờ một lời gọi nhỏ hơn cho tới khi trường hợp cơ sở trả lời.
Định nghĩa ngắn gọn

Hà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

  1. if number <= 1: return 1 là trường hợp cơ sở; thiếu nó các lời gọi sẽ không bao giờ dừng.
  2. return number * factorial(number - 1) gọi lại chính hàm đó với số nhỏ hơn.
  3. factorial(6) chờ factorial(5), factorial(5) chờ factorial(4), cứ thế xuống tới factorial(1).
  4. 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.factorial nhanh 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ụ

Chạy code →
main.py
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))
Lấy nút Run cho ví dụ này

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.

  1. 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.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đ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.
Chạy trong trình biên dịch Python →

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.

Sai
def factorial(number):
    return number * factorial(number - 1)
Cách sửa
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.

Tất cả thử thách