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ì.
- 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)fib(3)fib(2)fib(1)
fib(2)tính lại lần nữa
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.
@cache📓 Giữ một cuốn vở ghi đáp ánfibonacci(number - 1) + fibonacci(number - 2)🧮 Giải bằng hai câu hỏi nhỏ hơnif number < 2: return number🛑 Hai đáp án đầu tiên đã biết sẵnfibonacci(10)⚡ Mỗi đáp án nhỏ chỉ tính một lần: rất nhanhMemoization 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
if number < 2: return numbercho hai số hạng đầu, 0 và 1.fibonacci(number - 1) + fibonacci(number - 2)đi đúng theo định nghĩa.@cachetrongfunctoolsghi nhớ mọi kết quả, nên mỗifibonacci(k)chỉ chạy một lần.- 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ụ
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
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.
- 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
Đệ 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.
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
@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.
- Số Fibonacci Trả về số Fibonacci thứ n. Dễ
- Đếm Dãy Xúc Xắc Đếm số dãy kết quả gieo xúc xắc có thứ tự với tổng cho trước. Trung bình