Thuật toán Python

Fibonacci đệ quy với ghi nhớ (memoization) trong Python

Fibonacci đệ quy thuần tuý lặp lại cùng một phép tính hàng triệu lần. Thêm bộ nhớ đệm, nó chạy gần như tức thì.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • Viết Fibonacci bằng đệ quy
  • Vì sao bản thuần tuý tăng theo cấp số mũ
  • Ghi nhớ kết quả với functools.lru_cache
fib(4) khi không có bộ nhớ đệm
  • fib(4)
    • fib(3)
      • fib(2)
      • fib(1)
    • fib(2)tính lại lần nữa
Với @lru_cache, fib(2) lần thứ hai được đọc từ bộ nhớ đệm. fib(10) = 55.

Nhớ lại đáp án đã tính

Vấn đề

Định nghĩa đệ quy của Fibonacci rất đẹp nhưng chậm khủng khiếp: tính số hạng thứ 40 phải lặp lại cùng những phép tính nhỏ hàng trăm triệu lần. Ghi nhớ kết quả (memoization) khắc phục điều này chỉ bằng một dòng code, đồng thời cho bạn thấy một ý tưởng then chốt của quy hoạch động (dynamic programming).

Hình dung đời thường

Memoization giống một học sinh ghi mọi đáp án vào vở. Khi bị hỏi lại fib(5), bạn ấy không làm lại từ đầu mà đọc đáp án trong vở. Mỗi câu hỏi chỉ phải giải đúng một lần.

Từ cuốn vở ghi đáp án đến code
@cache📓 Giữ một cuốn vở ghi đáp án
fibonacci(number - 1) + fibonacci(number - 2)🧮 Giải bằng hai câu hỏi nhỏ hơn
if number < 2: return number🛑 Hai đáp án đầu tiên đã biết sẵn
fibonacci(10)⚡ Mỗi đáp án nhỏ chỉ tính một lần: rất nhanh
Lưu mỗi kết quả ở lần đầu; những lần sau dùng lại.
Định nghĩa ngắn gọn

Memoization lưu kết quả của mỗi lời gọi hàm theo đối số của nó, để các lời gọi lặp lại trả về kết quả đã lưu thay vì tính lại.

Những điểm quan trọng

  1. if number < 2: return number cho hai số hạng đầu, 0 và 1.
  2. fibonacci(number - 1) + fibonacci(number - 2) đi đúng theo định nghĩa.
  3. @cache trong functools ghi nhớ mọi kết quả, nên mỗi fibonacci(k) chỉ chạy một lần.
  4. Không có @cache, fibonacci(10) cần 177 lời gọi; có thì chỉ cần 11.

Khi nào nên sử dụng?

  • Hàm đệ quy lặp lại cùng các bài toán con: đường đi trong lưới, đổi tiền xu, tách từ.
  • Học ý tưởng đằng sau quy hoạch động.
  • Tăng tốc mọi hàm thuần (pure function) được gọi nhiều lần với cùng đối số.

Khi nào chưa cần

  • Hàm có tác dụng phụ hoặc kết quả thay đổi theo thời gian: cache sẽ trả về đáp án cũ.
  • Đệ quy rất sâu: dù có cache, fib(5000) vẫn có thể vượt giới hạn đệ quy; vòng lặp thì không.

Xem cách hoạt động

Nhấn Từng bước để theo từng lời gọi. Hãy để ý fib gọi lại cùng những giá trị nhỏ hơn nhiều lần, đó là lý do bản đơn giản chạy chậm.

Code ví dụ

Chạy code →
main.py
from functools import cache

@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

print(fibonacci(10))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

55

Giải thích code

Decorator @cache tự động ghi nhớ kết quả của hàm theo từng giá trị đầu vào. Khi fibonacci(8) đã được tính một lần, những lần gọi sau chỉ việc lấy kết quả có sẵn. Nhờ vậy, thời gian chạy giảm từ hàm mũ xuống còn O(n), đổi lại cần thêm O(n) bộ nhớ để lưu kết quả.

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

Đệ quy không có cache

Các giá trị giống nhau bị tính đi tính lại, và fib(40) mất nhiều giây.

Sai
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)
Cách sửa
@cache
def fibonacci(number):
    if number < 2:
        return number
    return fibonacci(number - 1) + fibonacci(number - 2)

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