Memoization reuses a function result when the same relevant inputs appear again. The recording applies this idea to Fibonacci, turning repeated recursive branches into lookups. The cache must describe the function's actual state and must distinguish a missing entry from a stored answer, including answers such as zero or false.
Cache the answer to a defined question
For a fixed Fibonacci definition, the integer n identifies the subproblem. After computing its answer, store that value under n. A later call can return it without expanding its children again. During one evaluation up to n, only a linear number of distinct nonnegative states need computation under the usual recurrence.
The base cases still matter. A cached recurrence that calls itself forever never produces a value to store. For recurrences that can revisit an active state, such as some graph problems, a completed-result cache alone is not enough to resolve a cycle. Define progress or retain additional active-state information when the problem needs it.
Treat zero and false as real results
A truthiness check loses valid stored answers. A path-existence calculation may correctly cache false, and a minimum-cost or count calculation may correctly cache zero. Use membership or a distinct missing marker. The cache's key must also include all relevant inputs; an amount solved with one coin set is not automatically reusable with another.
In a general JavaScript memoizer, object arguments introduce identity choices. Two separately allocated but equal-looking objects are distinct identity keys. Serializing inputs chooses another equivalence relation and can fail on cycles or discard distinctions. The JavaScript memoization guide provides a concrete receiver-and-argument identity contract, including promise rejection behavior.
Count states, transitions, and retained memory
Memoized Fibonacci uses linear stored state and linear recursion depth for its top-down form. Arithmetic cost grows with integer size if the result is not treated as bounded-width. A rolling bottom-up implementation can retain only the previous two values, but that is an additional storage optimization based on the recurrence's dependencies.
Continue with Bottom-Up vs. Top-Down, then study Vending Machine. Before adding a cache, write a sentence explaining the answer stored at each key and show a case in which two branches request that exact same state.
Count distinct solved states
The example returns the Fibonacci value and the number of states actually computed. For input 4, it returns [3, 5]: states 0 through 4 are each computed once. For input 0 or 1, only the requested base state is computed, so the state count is one.
A cache lookup must distinguish “not stored” from a stored value of zero. F(0) is zero and is a perfectly valid cached answer. A truthiness check would treat it as missing in some languages. The examples use presence checks or explicit optional results instead.
Keep the cache lifetime visible
A new cache is created for each top-level call. Calling the function twice therefore repeats its O(n) preparation, rather than sharing process-wide state. A global cache would need a different lifetime, memory, and concurrency discussion.
For n at least two, the function solves n + 1 distinct states. With fixed-width arithmetic, the total work and retained cache are O(n), and the recursive stack is O(n). Memoization removes duplicate subtrees but does not remove stack depth. A large n can still overflow the host stack or numeric range.
Test the base states and a small value with overlapping branches. Compare the state count with the naive call count to show what was saved. A correct final Fibonacci number alone cannot prove that memoization is effective; an implementation that recomputes every state might return the same value.
Python example and implementation choices
The in membership check tests whether a state was cached before reading its answer. This preserves F(0) = 0 without mistaking it for a miss. The local dictionary is fresh on each top-level invocation. Python arbitrary-precision arithmetic allows larger values than fixed-width versions, but recursive depth and the cost of larger additions still matter as inputs grow.
Worked example
def fib_memo_stats(n: int) -> list[int]:
memo = {}
def fib(value):
if value in memo:
return memo[value]
answer = value if value < 2 else fib(value - 1) + fib(value - 2)
memo[value] = answer
return answer
answer = fib(n)
return [answer, len(memo)]
Continue in Python
Open Memoization for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Python example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The Python interview preparation guide connects these language choices with further practice and the cross-language operation reference.