Overview
Make slow recursive functions instant by remembering results you've already computed — with one decorator from the standard library.
- Overlapping subproblems
- functools.lru_cache
- cache_info() to inspect the cache
Short Course
Recursive solutions often compute the same values many times.
@lru_cache stores each result the first time, so repeats are free.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
fib(80) # instant instead of taking ages
fib.cache_info() # CacheInfo(hits=78, misses=81, ...)
Task
Write count_paths(rows, cols): the number of ways to walk from the top-left
to the bottom-right cell of a grid, moving only right or down. Use recursion
with @lru_cache. A grid with a single row or column has exactly one path.
Test Suites
Pending
Stdout