Fibonacci & memoization

Algorithms & Problem Solving, lesson 2 of 6

🧠 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.

Example

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.

Walkthrough

The calls behind fib(5)

fib(5)= 5fib(4)= 3fib(3)= 2fib(2)= 1fib(1)= 1fib(0)= 0fib(1)= 1fib(2)= 1fib(1)= 1fib(0)= 0fib(3)= 2fib(2)= 1fib(1)= 1fib(0)= 0fib(1)= 1
Step 1 of 4

Every call with n >= 2 makes two more calls, until n < 2. That's the 15 calls the example counted for fib(5).

the first call
repeated work
answer read from the memo
Example

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. (That @ line is a decorator; the Functions module's Closures and decorators lesson shows how they work.)

Example

@lru_cache

cache_info() shows how often the cache saved work (hits) versus real computations (misses).

Quiz

What does this print?

Example

Bottom-up with a loop

No recursion, no cache, and it handles huge n.

Exercise

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) and ways(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.