Recursion & Memoization: Tăng tốc đệ quy với Top-Down Dynamic Programming
Hướng dẫn Recursion và Memoization bằng TypeScript: Top-Down DP, state, recurrence, cache key, độ phức tạp, stack overflow, async memoization và lỗi thường gặp.
ShanverseCập nhật 12 phút đọc— lượt xemĐang tải lượt xem
Dynamic Programming
Algorithms
Đệ quy chậm ở đâu?
Một hàm đệ quy có ba thành phần:
State: thông tin mô tả bài toán con.
Base case: trạng thái dừng.
Recurrence: cách kết hợp các bài toán con.
Fibonacci ngây thơ:
Cây gọi lặp lại cùng state:
fib(3), fib(2) và nhiều state khác bị tính nhiều lần. Recurrence thời gian gần:
nên tăng theo cấp số mũ, thường được mô tả là
Bình luận
O(2^N)
upper bound.
Memoization thay đổi điều gì?
Cache kết quả theo state n:
Có N+1 state khác nhau.
Mỗi state thực hiện O(1) work ngoài recursive calls.
Time: O(N).
Cache: O(N).
Call stack: O(N).
Dùng bigint vì Fibonacci sớm vượt Number.MAX_SAFE_INTEGER. Không trộn number và bigint trong phép toán.
Vì sao đây là Dynamic Programming?
Memoization hiệu quả khi bài toán có hai tính chất:
1. Overlapping subproblems
Nhiều nhánh gọi lại cùng một state.
2. Optimal substructure hoặc composable substructure
Đáp án state lớn có thể xây từ đáp án của state nhỏ hơn.
Không phải mọi recursion đều được tăng tốc mạnh bằng memoization. Duyệt một tree mà mỗi node chỉ thăm một lần vốn đã O(N); cache có thể chỉ thêm overhead.
0/1 Knapsack: N×Capacity states × 2 transitions → O(NC).
Memoization không tự biến mọi thứ thành O(N); nó loại bỏ việc tính lại state trùng.
Template Top-Down DP
Quy trình chuẩn:
Định nghĩa state tối thiểu nhưng đầy đủ.
Viết base case.
Liệt kê transitions.
Chọn cache key không va chạm.
Kiểm tra cache trước khi recurse.
Cache kết quả trước khi return.
memo.has() hay kiểm tra truthy?
Sai:
Kết quả hợp lệ có thể là 0, false, "" hoặc null.
Đúng:
Hoặc dùng cached !== undefined chỉ khi undefined không phải kết quả hợp lệ.
Ví dụ 1: Đếm đường đi trong Grid có vật cản
State là (row, column).
State count: tối đa R×C.
Time: O(RC).
Cache: O(RC).
Stack depth: O(R+C).
Key row * columns + column chỉ an toàn vì columns cố định và state nằm trong grid.
Ví dụ 2: Coin Change — số coin ít nhất
Cho coin denomination dương, tìm số coin ít nhất để tạo amount.
Nếu A là amount và C là số loại coin:
States: A+1.
Transitions mỗi state: C.
Time: O(AC).
Space: cache O(A), stack có thể O(A/minCoin).
Coin 0 hoặc âm sẽ tạo transition không tiến triển/cycle, nên phải validate.
Ví dụ 3: 0/1 Knapsack
State (index, remainingCapacity):
Time/space pseudo-polynomial O(N×Capacity), không phải polynomial theo số bit dùng để biểu diễn capacity.
Nếu capacity lớn nhưng chỉ ít state reachable, Top-Down có thể tránh tính nhiều cell mà Bottom-Up phải duyệt.
Ví dụ 4: Longest Common Subsequence
State (leftIndex, rightIndex):
Time và cache tối đa O(MN), stack O(M+N).
JavaScript index string theo UTF-16 code unit. Nếu “character” phải là Unicode code point hoặc grapheme, normalize/segment trước và chấp nhận memory bổ sung.
Chọn Cache Key đúng
Cache key phải chứa mọi dữ liệu ảnh hưởng đến kết quả.
Sai:
Đúng:
Rủi ro của string key
Separator collision nếu state chứa string tùy ý.
JSON.stringify() phụ thuộc cấu trúc/order và có chi phí.
Object mutable có thể đổi sau khi tạo key.
BigInt không stringify mặc định.
Với state số nhỏ, có thể encode thành integer. Với state object, dùng nested Map hoặc registry ID ổn định.
Generic memoize cho pure function
Chỉ an toàn nếu:
Hàm deterministic/pure theo key.
Key gồm tất cả dependencies.
Input không bị mutate theo cách làm result cũ hết hạn.
Cache lifetime/bounds phù hợp.
Trong DP, explicit memo bên trong solver thường rõ hơn generic wrapper.
Recursive function và self-reference
Một lỗi phổ biến:
fibonacciSlow vẫn gọi chính nó, không gọi wrapper memoizedFib, nên recursive calls không đi qua cache.
Giải pháp:
Truyền memo rõ ràng như các ví dụ.
Dùng closure trong đó recursive call gọi hàm đã cache.
Dùng fixed-point style cẩn thận.
Async Memoization và request deduplication
Cache Promise ngay khi tạo, không chờ resolve, để các caller đồng thời dùng chung request:
Cần quyết định:
Có cache rejection không?
TTL bao lâu?
Max entries?
Có stale-while-revalidate không?
Cancellation của một caller có được hủy request chung không?
Key có tenant/user/auth context không?
Không dùng global memo cache cho dữ liệu phân quyền nếu key thiếu tenant/user; đó có thể là data leak.
Cache Scope và Memory Leak
DP thường nên tạo memo mỗi lần solve:
Global cache sống mãi có thể:
Tăng memory không giới hạn.
Giữ object không được garbage collect.
Trả stale result.
Trộn dữ liệu giữa request/tenant.
General application cache cần TTL, capacity, eviction, metrics và invalidation; đó là bài toán khác với memo table hữu hạn của một lần chạy DP.
Stack Overflow: Memo nhanh hơn nhưng vẫn sâu
Memoization giảm số call lặp lại, không giảm độ sâu của một path.
JavaScript engine có call stack hữu hạn và không nên dựa vào tail-call optimization phổ quát.
Giải pháp:
Bottom-Up DP.
Vòng lặp iterative.
Explicit stack/trampoline.
Chia nhỏ công việc hoặc đổi recurrence.
Fibonacci iterative:
Time O(N), auxiliary space O(1), không có recursive stack.
Top-Down và Bottom-Up
Bắt đầu Top-Down để đúng recurrence, sau đó chuyển Bottom-Up nếu profiling cho thấy stack/constant overhead là vấn đề.
Cycle trong State Graph
Top-Down DP thường chạy trên DAG ngầm. Nếu transition quay lại state đang tính, chỉ cache sau khi tính xong sẽ không ngăn infinite recursion.
Dùng trạng thái visiting khi cycle có thể xuất hiện:
Nếu cycle có ý nghĩa toán học, có thể cần graph algorithm, fixed-point iteration hoặc shortest-path method thay vì recursion đơn giản.
Khi Memoization không giúp
Mỗi recursive state chỉ xuất hiện một lần.
Cache key gần như luôn unique.
Chi phí hash/key lớn hơn computation.
Function có side effects cần chạy mỗi lần.
Result phụ thuộc time, random, I/O hoặc global mutable state không có trong key.
Cache quá lớn so với memory budget.
Input thay đổi nhưng cache không invalidation.
Luôn đo cache hit rate và runtime thay vì hứa một hệ số tăng tốc cố định.
Lỗi thường gặp
1. Cache sau recursive call nhưng không kiểm tra trước
Sẽ không loại computation trùng.
2. Key thiếu state
Hai bài toán con khác nhau bị coi là một và trả đáp án sai.
3. Dùng truthiness cho cache
Bỏ lỡ 0, false, null.
4. Base case sai hoặc không tiến triển
Recursion không kết thúc.
5. Global cache không giới hạn
Memory leak/stale data/cross-tenant leak.
6. Cache side effect
Memoization sẽ bỏ qua side effect ở cache hit.
7. Mutation sau khi cache
Kết quả không còn phản ánh input hiện tại.
8. Quên giới hạn call stack
Time đã tuyến tính nhưng vẫn crash vì recursion sâu.
9. Cache Promise rejection mãi mãi
Một lỗi tạm thời có thể poison cache; thường nên evict khi reject.
10. Gọi mọi cache là Dynamic Programming
Memoization một API call là caching; Top-Down DP dùng memo để giải recurrence có overlapping subproblems. Kỹ thuật liên quan nhưng mục tiêu/lifetime khác nhau.
Testing checklist
Base cases nhỏ nhất.
Input invalid và boundary.
Kết quả 0, false, null nếu hợp lệ.
Nhiều path đến cùng state.
Cache hit thực sự xảy ra.
So sánh brute force trên input nhỏ.
Random/property-based test giữa Top-Down và Bottom-Up.
Recursion depth cực lớn.
State graph có cycle.
Object input bị mutate.
Async concurrent callers chỉ gọi loader một lần.
Async rejection được retry.
Cache key có tenant/auth context.
Memory được giải phóng sau một lần solve.
Quy trình chuyển recursion thành Top-Down DP
Viết recursion đúng trước.
Liệt kê toàn bộ biến tạo thành state.
Xác nhận overlapping subproblems.
Chọn key ổn định, không va chạm.
Kiểm tra memo ngay sau base case hoặc trước work đắt.
Cache mọi result hợp lệ, kể cả 0/false.
Phân tích states × transitions.
Tính cả cache space và stack depth.
Thêm cycle protection nếu state graph không chắc là DAG.
Chuyển Bottom-Up/iterative nếu stack hoặc overhead là bottleneck.
Kết luận
Memoization biến cây recursion lặp lại thành graph state được tính một lần:
Top-Down DP đặc biệt hiệu quả khi bài toán có overlapping subproblems và chỉ một phần state space reachable. Nhưng tốc độ không miễn phí: cache dùng memory, recursion vẫn có stack limit, key sai làm kết quả sai và global cache có thể rò rỉ dữ liệu.
Một implementation tốt phải định nghĩa state đầy đủ, base case đúng, key ổn định, cache scope rõ, phân tích số state × transitions và sẵn sàng chuyển Bottom-Up khi input quá sâu.
