Memoisation: Caching Recursive Results

Naive recursive Fibonacci computes the same values repeatedly. fib(5) calls fib(4) and fib(3); fib(4) calls fib(3) and fib(2) — so fib(3) is computed twice. This redundancy grows exponentially: fib(40) makes over one billion function calls. Memoisation solves this by storing each result the first time it is computed, so subsequent calls retrieve it in O(1) rather than recomputing it.

Add a memo dict as a parameter (or a closure). Before computing, check if the answer is already in memo. If yes, return it immediately. If no, compute it, store in memo, and return. Every unique sub-problem is now computed exactly once, turning O(2^n) into O(n) time and O(n) space for the memo dict plus O(n) stack space.

Python provides @functools.lru_cache(maxsize=None) (also available as @functools.cache in Python 3.9+) to automate memoisation. Adding this decorator above a function caches all calls by their arguments. maxsize=None means unlimited cache size — every unique argument combination is cached. This converts any recursive function into a memoised version with one line of code.

LeetCode 70 'Climbing Stairs': you can climb 1 or 2 steps at a time. How many ways to reach step n? This is Fibonacci in disguise: ways(n) = ways(n-1) + ways(n-2). Base cases: ways(0) = 1 (one way to stay at ground), ways(1) = 1. With memoisation, O(n) time and O(n) space.

LeetCode 322 'Coin Change': given denominations and a target amount, find the minimum number of coins. Top-down memoised recursion: dp(amount) = 1 + min(dp(amount - coin)) for each valid coin. The base case: dp(0) = 0. Cache each sub-amount. If a sub-amount is impossible, return infinity. Memoisation turns the exponential brute force into O(amount × len(coins)) time.

LeetCode 139 'Word Break': determine if a string can be segmented into dictionary words. Top-down recursion: can_break(s, start) tries every prefix s[start:end]; if it is in the dictionary and can_break(s, end) is true, return true. Without memo this is O(2^n); with memo (caching each start index) it becomes O(n² × L) where L is the max word length.

Memoisation (top-down) starts with the original problem and caches answers as they are discovered recursively. It solves only the sub-problems that are actually needed. Tabulation (bottom-up) pre-fills a table from small sub-problems to large, solving all sub-problems regardless. Memoisation is easier to derive from a recursive solution; tabulation avoids recursion-depth limitations and function-call overhead.

Many DP problems that memoised recursion solves in O(n) space can be further optimised to O(1) space when only a fixed number of previous sub-problem answers are needed. For Fibonacci: only the last two values matter. For climbing stairs: same. Rolling two variables replaces the entire memo dict or table.

Three ways to implement memoisation manually. A global dict is simple but pollutes module scope. A closure encapsulates the cache within the function, preventing leakage but requiring a wrapper. @lru_cache is the cleanest — one decorator replaces all boilerplate. In an interview context, start with @lru_cache unless the interviewer specifically asks for a manual implementation.

Memoisation only accelerates problems with overlapping sub-problems — cases where the same sub-problem is computed multiple times. If every sub-problem is unique (like in simple tree traversal where each node is visited exactly once), memoisation adds overhead without benefit. Also, memoisation cannot fix problems where the recursive tree is exponential in the number of distinct sub-problems rather than in reuse — those require a different algorithm altogether.

Apply memoisation when: you have a recursive solution that is correct but slow due to redundant recomputation, the function has a small number of distinct argument combinations, and the return value depends only on the arguments (pure function — no side effects, no global state). Check the sub-problem state space: if there are at most O(n) or O(n²) distinct states, memoisation converts exponential to polynomial time.

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

In this lesson you learned: memoisation stores results of sub-problems to avoid recomputation, converting exponential recursion to polynomial time, @functools.lru_cache is the idiomatic Python tool requiring only one line, and memoisation (top-down) and tabulation (bottom-up) are the two styles of DP — memoisation is easier to derive, tabulation avoids stack depth issues. Congratulations — you have completed the recursion and hash-map modules!