Memoize Pure Functions with lru_cache
Use functools.lru_cache on a deterministic function and verify both results and cache reuse.
Example check: Worked and guided code samples are checked against CPython 3.13. Practice uses Pyodide 0.29.5 (Python 3.13) in your browser. How we check lessons
Video lesson: Memoize Pure Functions with lru_cache
The preview is stored on this site. YouTube loads only when you press Play. Watch on YouTube
Jump to a chapter
Read the video transcript
Select a timestamp to watch that moment on YouTube.
- 00:00
A function can return the right answer and still do far more work than necessary. Naive recursive Fibonacci is a compact example. Fib six calls fib five and fib four; fib five calls fib four again, and many smaller branches repeat. We will measure the call count rather than merely claim that repetition occurs. Then we will use functools.lru_cache to store results for previously seen arguments and inspect the cache statistics. The cache makes sense because this mathematical function returns the same value for the same nonnegative integer every time. It would be dangerous to apply the same idea blindly to a changing file, current time, random result, or live price.
- 00:44
The companion lesson has runnable examples, a checked function, common mistakes, and a quiz. Before the first run, predict fib six. The standard sequence begins zero, one, one, two, three, five, eight. The answer is eight. Now make a second prediction: will the program call the function only seven times for the seven distinct input values zero through six? The counter will show why naive recursion says no. This lesson separates correctness, the work performed, and the memory cost of keeping cached answers. The result is eight, which is correct. But the counter reaches twenty-five function calls.
- 01:25
Only seven different n values are needed for inputs from zero through six, so many of those calls repeat work. The global counter is just a measurement instrument for this demonstration; it is not part of the Fibonacci calculation. If we call fib six again, the same recursive tree is evaluated again because nothing is stored. As n grows, this waste becomes much larger. Memoization means remembering an answer by its input and returning it when the same input appears. Python's lru_cache wraps a function and maintains that mapping for us. The word cache does not mean faster in every case. If a function is cheap and each argument appears once, lookup and storage might be unnecessary overhead.
- 02:11
It also uses memory. Before adding a decorator, ask whether the function is pure enough: for a given n, can we trust the result to remain the same during the cache lifetime? Mathematical Fibonacci meets that requirement. A function reading a mutable external source might not. We will inspect a tiny cached function next, using its cache_info method to make reuse observable rather than relying on a vague speed impression. The first call with seven is a miss: square executes and stores forty-nine under the key seven. The second call with the same argument is a hit and reuses the stored value.
- 02:51
Both printed results are equal, so the hit and miss counts are the evidence of reuse. maxsize=None means entries are not automatically evicted by size. That is convenient for a small bounded set of Fibonacci inputs, but an unbounded stream of unique arguments can keep growing memory. A positive maxsize creates a least-recently-used cache that evicts older entries when full. The arguments must also be hashable. Integers work; a mutable list cannot be a cache key. A tuple of integers can be hashable if all its parts are hashable. The cache wrapper exposes cache_info and cache_clear, which are useful when measuring behavior or invalidating stored results.
- 03:36
Be careful about exceptions and side effects: caching a function that reads the clock or file contents may return yesterday's result for today's call. We will now decorate Fibonacci itself. Recursive calls go through the wrapper, so overlapping branches can reuse smaller answers. We will also reject negative input explicitly; without that guard, the recurrence moves away from the base cases and can recurse indefinitely. Fib ten returns fifty-five on both calls. The last line confirms that the wrapper recorded at least one cache hit; there are overlapping recursive subproblems during the first call, and the second top-level call is another reuse.
- 04:19
We do not hard-code a specific hit count into the function's contract, because the count depends on the call history and implementation. The result contract is the Fibonacci sequence, while cache_info is an observation of the optimization. The negative guard raises ValueError before trying fib of an even smaller negative number. Zero and one are base cases. Every other nonnegative n reduces to n minus one and n minus two, so those branches eventually reach the bases. maxsize=None is acceptable for this teaching example, but a service receiving many unrelated keys should consider a bounded cache and an invalidation policy.
- 05:02
The decorator does not make every recursive algorithm safe or fast: deep recursion still has a stack limit, and large integer results still take space. We are using it where repeated deterministic arguments make the benefit clear. In the browser task, implement the recurrence without removing the decorator. The checker will verify values, negative rejection, and an observable cache hit after a repeated call. The sequence assertion covers both base cases and several recurrence steps. The negative test expects ValueError and fails loudly if the guard is missing. We then call fib twelve, record the current hit count, call the same value again, and require hits to increase.
- 05:47
That is a direct check that the wrapper really caches, not just a function that happens to compute the right number. The last print line appears only after all of these assertions pass. When you complete the browser exercise, keep the order of conditions: reject negatives, return n for zero or one, and otherwise add the two smaller calls. If an implementation returns correct values but lacks cache_info, check that @lru_cache is still applied to the function being called. Also remember that caching is a tradeoff. It exchanges memory for fewer repeated computations and assumes a stable mapping from arguments to results.
- 06:27
When those assumptions fail, the correct solution may be no cache, a short-lived cache, or an explicit cache key containing a version. For this recurrence, the assumptions are clean, which lets us see the mechanism without a network or database. Measure reuse, verify semantics, then decide whether caching belongs in a real application.
Understand the concept
Memoization stores the result of a function call and reuses it when the same arguments appear again. In naive recursive Fibonacci, the same smaller Fibonacci values are computed many times. functools.lru_cache wraps a function with a cache keyed by its hashable arguments. Applying @lru_cache(maxsize=None) keeps all computed values until the cache is cleared or the process ends.
Caching is appropriate for functions whose result depends only on their arguments. A function that reads a changing file, clock, random number, or mutable global state can return stale results when cached. The arguments must be hashable; passing a list to an lru_cache-wrapped function raises TypeError. A tuple of immutable values may work when its elements are also hashable.
The task implements a nonnegative Fibonacci function fib(n). It must raise ValueError for negative input and return the standard sequence 0, 1, 1, 2, 3. Decorate the function with lru_cache so repeated calls can be observed through fib.cache_info(). Hits and misses are observations, not proof that every workload will become faster. The cache uses memory, and an unbounded cache can grow without limit.
For a bounded cache, set maxsize to a positive number. Least recently used entries are discarded when the cache fills. Clear caches when their underlying assumptions change. In this exercise, the recurrence is mathematical and stable, so cached results remain valid. Validate input before recurrence so a negative value cannot recurse forever.
- Memoization reuses results for matching arguments
- lru_cache requires hashable arguments
- Pure functions are safe cache candidates
- cache_info exposes hits, misses, and size
See it step by step
Read the code, predict the output, then compare it with the result.
01. Count repeated calls without caching
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))
print(fib(6))8
8Both calls return eight, but the second call recomputes the entire recursion tree.
02. Inspect a cache hit
from functools import lru_cache
@lru_cache(maxsize=None)
def square(n):
return n * n
print(square(7))
print(square(7))
print(square.cache_info().hits)
print(square.cache_info().misses)49
49
1
1The first call computes and stores 49; the second uses the cached value.
A closer look
Follow the reasoning, inspect each result, then try the suggested changes in the console below.
See the repeated work in a recursive tree
Naive Fibonacci recomputes the same smaller arguments many times. The function returns a correct value, but correctness alone does not tell us how much work happened. Count each invocation as the recurrence expands. For n equal to six, there are many more function calls than distinct input values.
The counter is deliberately outside the function here only to observe work, not to compute the sequence. Two independent calls perform the same recursive tree again when nothing is cached. A bigger n makes this duplication grow quickly. Before adding a cache, first verify that the function's result depends only on n; otherwise stored values could become stale.
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))
print(calls)8
25- fib(6) returns the correct eighth sequence value.
- The counter records every recursive call.
- Many calls repeat the same smaller n values.
Measure cache hits instead of assuming improvement
functools.lru_cache wraps a function and stores results under its arguments. With maxsize=None the cache does not evict entries automatically. The first call to square(7) is a miss because seven has no stored result. The second is a hit and returns the same answer without executing the wrapped calculation again.
cache_info reports hits, misses, maximum size, and current size. This is a useful measurement when a real workload repeats arguments. It does not guarantee a speedup for a function called only once per unique input. The arguments must be hashable, and the computation should be deterministic for those arguments.
from functools import lru_cache
@lru_cache(maxsize=None)
def square(number):
return number * number
print(square(7))
print(square(7))
print(square.cache_info().hits)
print(square.cache_info().misses)49
49
1
1- The first call stores 49 under key seven.
- The second call reuses the stored result.
- cache_info makes the reuse observable.
Cache the recurrence but keep its input contract
The exercise decorates fib itself, so recursive calls also pass through the cache. Each distinct nonnegative n is computed once and can be reused by later branches. The negative-input guard matters because the recurrence would otherwise continue away from its base cases. A cached exception is not the goal; the function should reject invalid input clearly.
After the first fib(10) call, reading cache_info shows hits from the overlapping branches. A second fib(10) call adds another hit. Do not hard-code an exact hit count into application logic: implementation changes and call order can change it. The task checker asks only for correct values, explicit negative rejection, and observable cache reuse.
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 0:
raise ValueError('n must be nonnegative')
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10))
print(fib(10))
print(fib.cache_info().hits > 0)55
55
True- Validate before the recursive step.
- Base cases stop at zero and one.
- A repeated call is served from cached results.
Try it in Python
Edit the example and run it. Python starts in your browser the first time you click Run.
Python console
Ready to runNeed input()? Add one value per line
Your output appears here.
Need a hint?
Check n < 0 first. Then return n when n < 2. Recursively add the two smaller calls. Do not remove @lru_cache.
Complete the task and select Check task to verify your code.
Quick quiz
Three questions. You can change your answers and try again.
Typical mistakes
Everyone meets these errors. See what causes them and how to fix them.
Caching changing external state
@lru_cache(maxsize=None)
def current_price(item):
return read_live_price(item)def current_price(item):
return read_live_price(item)What happens: Later calls may reuse an old price.
A changing data source needs an explicit refresh or cache invalidation policy.
Passing an unhashable list as a key
@lru_cache(maxsize=None)
def total(values):
return sum(values)
print(total([1, 2]))@lru_cache(maxsize=None)
def total(values):
return sum(values)
print(total((1, 2)))What happens: TypeError: unhashable type: 'list'.
A tuple of integers is hashable and can be used as a cache key.