🧠 Algorithms & Problem Solving, lesson 2 of 6
Fibonacci & memoization
Turn painfully slow recursion into instant answers by caching results.
10 min
1 exercise
1 quiz
0/2 solved
Getting Python ready… examples can run in a moment.
In the Fibonacci sequence each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21...
Written recursively it's beautifully short, but it hides a trap. Let's count how many calls it makes.
Counting the calls
The work multiplies by about 1.6 for every step up.
fib(40) would need over 300 million calls, because
the same values are recomputed again and again.
Memoization means remembering answers you've already computed. Keep a dict: before doing the work, check whether the answer is already stored.
A hand-made memo
Each value is now computed only once, so fib(100)
is instant.
Let functools do it. Put
@lru_cache(maxsize=None) (or simply @cache) above
a function and Python memoizes it for you. The
arguments must be hashable: numbers, strings and
tuples work; lists don't.
@lru_cache
cache_info() shows how often the cache saved work
(hits) versus real computations (misses).
What does this print?
Bottom-up with a loop
No recursion, no cache, and it handles huge n.
Climbing stairs
You climb a staircase taking 1 or 2 steps at a
time. ways(n) is the number of different ways to
reach step n:
ways(0)andways(1)are both 1- otherwise
ways(n) = ways(n - 1) + ways(n - 2)
Write it recursively and add @lru_cache so
ways(80) is instant.