Lessons · Python · memoising (not doing it twice)
Remember what you already worked out
When a recursion asks the same smaller question down more than one branch, store each answer the first time. The code barely changes; the cost changes class.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
It is the difference between a function that answers in a blink and one that never finishes. It is also the honest half of 'dynamic programming', which is a grand name for not doing the same work twice.
How to think about it
Write the plain recursion first, because it is easier to get right. Then ask whether any subproblem is reached by more than one route. If it is, add @lru_cache and change nothing else.
Worked example
import functools
calls = 0Count how much work the plain version does.
def fib(n):
global calls
calls += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)fib(n-2) is computed again inside fib(n-1).
fib(20)
print(calls)21891
@functools.lru_cache(maxsize=None)One line, added above the same function.
def cached_fib(n):
return n if n < 2 else cached_fib(n - 1) + cached_fib(n - 2)Identical body.
cached_fib(20)
print(cached_fib.cache_info().misses)21
Your turn
Make the recursion remember its answers.
import functools
@functools.(maxsize=None)
def ways(n):
return 1 if n < 2 else ways(n - 1) + ways(n - 2)Solve one with the tests running
The trap
Caching only pays when subproblems OVERLAP. On a recursion where every branch is a fresh question, the cache stores misses and buys nothing but memory. It also needs hashable arguments, so a list argument raises.