Memoization & Top-Down Dynamic Programming
You'll learn to
- -Add memoization (caching) to a recursive function to eliminate redundant work
- -Use functools.lru_cache as the built-in shortcut for memoization
- -Understand top-down DP as distinct from (but related to) bottom-up tabulation
The last chapter diagnosed the exact disease behind naive recursive Fibonacci: redundant recomputation of the same subproblems, over and over. This chapter fixes it directly, with memoization - caching the result of a computation so that if the same input ever shows up again, the answer is looked up instead of recomputed.
Adding a Cache By Hand
Every distinct fib(k) is now computed exactly once and stored; any later call for that same k becomes an O(1) dict lookup instead of branching into two more recursive calls. This collapses the call tree from exponential branching down to O(n) time (and O(n) space for the cache), turning what would have been hundreds of millions of calls for fib(40) into a mere 40.
functools.lru_cache: Memoization Built In
Manually threading a cache dict through every recursive call, as above, gets tedious and error-prone once a function has other callers unaware of that extra parameter. Python's standard library already provides this: decorate any pure function - same input always producing the same output, with no side effects - with functools.lru_cache, and Python transparently caches every call by its arguments.
maxsize=None means the cache never evicts old entries, which is fine for something like Fibonacci where the realistic input space stays small - though a real maxsize is worth setting for any function called with a huge variety of arguments over a long-running program, so the cache itself does not grow without bound.
This Is "Top-Down" Dynamic Programming
What was just built has a name: dynamic programming (DP) - solving a problem by breaking it into overlapping subproblems and reusing previously computed answers rather than recomputing them. This specific flavor is called top-down: start from the original question, fib(n), recurse toward smaller subproblems, and cache answers as they are produced, on the way down the call tree. A second flavor, bottom-up (also called tabulation), instead starts from the smallest subproblems and iteratively builds up to the final answer with no recursion at all - typically a simple loop and an array or a couple of variables, sidestepping the call-stack depth concern entirely. Bottom-up DP gets its own full treatment later in this course; for now, the important thing to recognize is that memoization is dynamic programming approached from the recursive direction already familiar from this chapter.
- -Overlapping subproblems - the same smaller input recurs many times across the call tree, like fib(3) inside fib(5)'s tree.
- -A pure function - safe to cache, since it does not depend on any mutable outside state.
- -A recursive solution that is already correct, but too slow specifically because of redundant recomputation.
Not every slow recursive function has overlapping subproblems - merge sort, in a sibling module, recurses heavily too, but each subproblem is a distinct sub-range of the array, so there is nothing worth caching. Memoization only helps when the exact same subproblem would otherwise be solved more than once.
What makes naive recursive Fibonacci exponential rather than linear?
Level 7: Recursion & Memoization asks you to write recursive solutions that use memoization and caching to avoid redundant recomputation - exactly the fib_memo and @lru_cache pattern above, applied to whatever recursive subproblems the level's specific functions define.