Memoization Tricks That Make Python Recursion Fly

Recursive functions feel like magic when you first encounter them. A few lines of Python can express an idea that would take pages of imperative code, and the elegance is real. The catch shows up the moment you feed your function real data. A naïve Fibonacci implementation chokes on the 50th term, and what looked tidy in the REPL becomes a liability in production. That's where memoization earns its keep, transforming exponential blow-ups into near-linear walks through the same problem space.

Australian developers run into this wall in familiar settings. A developer in Sydney might be profiling a tree traversal for a fintech dashboard during their arvo break, while a Brisbane team hammers a combinatorial search for a logistics startup. Even hobbyists working through LeetCode solutions on the train from Parramatta to the CBD feel the slowdown as recursion stacks pile up. The fix is rarely a rewrite; it's a small cache that remembers answers already paid for.

What Goes Wrong Without a Cache

In a standard recursive function, every call fans out into more calls. The classic Fibonacci example computes fib(n) by adding fib(n-1) and fib(n-2). Each branch spawns two more branches, and the work compounds. For fib(35), you're doing roughly 29 million additions, even though only 36 distinct values exist. The repeated recomputation is the real cost, and it grows without bound as the input rises.

Python doesn't help you here by default. Each recursive call pushes a new frame onto the call stack, holds onto local variables, and waits for results. The interpreter also evaluates default arguments, builds tuples, and allocates integers. None of that is free. On a laptop in Adelaide during a long summer evening, the fans spin up just to compute a number that fits in 64 bits, and the slowdown is unmistakable.

The same pattern haunts more practical algorithms. Counting the number of paths through a grid, breaking down change-making problems, or evaluating certain grammar parsers all share the structure of overlapping subproblems. Without somewhere to store the answers, you'll pay for each one again and again, even when the answer hasn't changed.

The Core Idea Behind Memoization

Memoization is a deliberate cache of computed results. You give a function a memory: each time it runs with a particular argument, it checks the cache first. If the answer is there, it returns instantly. If not, it computes, stores, and returns. The next caller with the same argument skips straight to the saved result. The cache effectively turns a tree of recomputation into a directed acyclic graph that gets walked once.

This works because recursive functions with overlapping subproblems visit the same states repeatedly. The recursion tree for Fibonacci visits fib(5) dozens of times. With a memo, fib(5) runs once and is reused everywhere it appears. The reduction is dramatic: fib(35) drops from roughly 30 million calls to about 70, and fib(100) becomes a calculation rather than a process that runs until lunchtime.

You can think of it as a small notebook on the desk of a developer in Melbourne's CBD. The notebook holds the answers to questions you've already chased down. Pull the answer out instead of re-reading the textbook. In Python, this notebook is usually a dictionary, keyed by the function's arguments.

Building a From-Scratch Memoizer

A bare-bones memoizer is just a dictionary wrapped around a function. Python's closure rules make it easy to write one in a dozen lines. The shape is straightforward: define a wrapper that checks if the args are in a cache dict, and if not, runs the original function, stashes the result, and returns it.

def memoize(fn):
    cache = {}
    def wrapped(*args):
        if args not in cache:
            cache[args] = fn(*args)
        return cache[args]
    return wrapped

Apply it with the @memoize decorator and any function benefits. The wrapper uses a tuple of arguments as the dictionary key, which works for hashable types like integers, strings, and tuples. Lists and dicts won't work as keys unless you convert them into a stable form first, which is a common stumbling block in interview prep sessions.

The hand-rolled version is great for learning and for situations where you want full control. You can add eviction policies, custom key transformations, or instrumentation that counts cache hits. It's also handy when you're working in constrained environments where pulling in extra modules feels heavier than the problem warrants.

functools.lru_cache for Production Code

For real-world work, Python's standard library offers functools.lru_cache, a memoization decorator built by people who've thought hard about edge cases. You slap it on a function, optionally pass maxsize, and you're done. The "lru" stands for least recently used, which means the cache evicts old entries when it fills up rather than holding onto everything forever.

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

The decorator handles hashable arguments, thread safety in the common case, and fast lookup. It's the version a Sydney-based quantitative team would reach for, especially when the function shows up in a tight loop inside a backtest. The LSTM network write-up on the site touches on a related idea, where stateful sequence models remember past activations to skip redundant computation across time steps.

maxsize deserves real attention. Set it to None and the cache grows without bound, which is fine if your input space is naturally bounded. For something like fib(1000), the unconstrained cache holds around 1000 entries and uses little memory. For a function over arbitrary user-provided strings, you'd want a cap to keep your process from ballooning past the limits of a typical 16GB workstation in a Perth co-working space.

Parameters worth knowing on lru_cache

• maxsize: caps the cache. None means unlimited, while an integer sets the entry count before evictions begin.
• typed: when True, treats 1 and 1.0 as distinct keys, which matters for functions that care about exact types.
• cache_info(): a method on the wrapped function that returns hits, misses, maxsize, and currsize for quick profiling.
• cache_clear(): empties the cache, useful when the underlying data source has been refreshed and old answers are stale.

Applying Memoization to LeetCode and Interview Problems

LeetCode problems often hide memoization behind a familiar shape. Coin change, climbing stairs with variable jumps, longest common subsequence, and many tree DP questions all reward a small dictionary of saved sub-answers. The trap is to reach for dynamic programming tables when a top-down recursive memoization reads far more naturally and stays closer to the recurrence itself.

A developer prepping for interviews at Canva in Surry Hills, or practising during a commute on the NBN-fuelled train down the Illawarra line, often finds the top-down form easier to reason about. You write the recurrence as a recursive function, then add a cache. The mapping from recurrence to code is direct, and you avoid the off-by-one errors that plague bottom-up conversions when the indexing gets fiddly.

Memoization also shines in problems with sparse state spaces. If only a handful of subproblems are reachable, a dict-based memo saves memory compared to a full DP table. That's a real win when you're processing thousands of test cases in a loop on a machine that already runs hot through a Brisbane summer, and you want to keep the working set tight.

Memory Trade-offs and When Not to Memoize

Memoization trades memory for speed, and the bill comes due eventually. Every cached result sticks around until eviction or process exit. For functions over a small, fixed domain, that's a bargain. For functions over unbounded domains, the cache can swallow RAM faster than you'd expect, especially when argument tuples include strings or large objects that retain references to data you thought you'd released.

There are also functions where memoization simply doesn't help. If each call has unique arguments, the cache fills with entries that are never reused. Pure recursive walks that visit distinct nodes, like traversing a fresh tree once, gain nothing from a memo. The same is true when the function has side effects, like logging or mutating a global counter. A memoizer would skip the side effect on cache hits, breaking your invariants in subtle ways that only surface under load.

Watch for mutable arguments. Passing a list to a memoized function and then mutating that list breaks the contract, because the cache key refers to the original tuple form, not the current contents. In a Python codebase at a Melbourne fintech, this kind of bug surfaces during integration tests where the same list gets passed in repeatedly with subtle mutations between calls and the cache quietly hands back stale answers.

Cases where memoization can hurt

• Functions with side effects, where a cache hit skips the work you actually wanted to run.
• Arguments that mutate between calls, which silently produce stale or wrong results from the cache.
• Unbounded input spaces, where the cache grows until memory pressure forces a swap and slows everything down.
• Recursive walks over unique structures, like parsing a single fresh document once, where every state is visited only a single time anyway.

Patterns Beyond Pure Recursion

Memoization isn't only for textbook recursion. It speeds up regular expression engines with backreferences, parser combinators, and any function that exhibits referential transparency with bounded input. In machine learning pipelines, you sometimes see memoized feature transformations, where the same input gets transformed repeatedly and caching saves redundant work across an epoch loop.

If you're chasing a broader picture of how caching intersects with algorithms and data structures, the machine learning hub on helloml.org collects related write-ups, including ones on boosting and tree-based models that use similar memo-like state across splits. The connection isn't accidental. Many ML algorithms rest on recursive decompositions that benefit from cached sub-results, and the patterns rhyme with each other in useful ways.

A practical pattern is to memoize the expensive leaf of a pipeline. If a function precomputes a large lookup table from a slow data source, wrap it in lru_cache with a sensible cap. When the source changes, you call cache_clear() to invalidate. The pattern is common in Australian data teams working with ABS economic releases, where the same census tract aggregates get queried many times per report and the source updates only quarterly. The cache turns dozens of identical fetches into a single slow one followed by cheap reads, which is the whole point of the technique.