Fibonacci memoization

Speed up recursive Fibonacci with memoization.

Fibonacci memoization

Speed up recursive Fibonacci with memoization: store each n's result in a dictionary.

Compute and store on first call; return the stored value on later calls.

This small change drops fibonacci from Θ(2^n) to Θ(n); a big difference.

Dictionary check

First check if n is in the cache. If yes return directly; else compute and store.

This ensures each subproblem is solved only once.

The cache check is the heart of memoization; it must be implemented correctly.

Exercise Fibonacci memo

Write fib_memo(n, memo). Recursive Fibonacci with memoization. Print 55 with print(fib_memo(10, {})).

Show example solution

def fib_memo(n, memo):
    # Fibonacci memo
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]
print(fib_memo(10, {}))

Test yourself

Cache check
```
if n in ____:
```
Show answer
```
if n in memo:
```
Fibonacci memoization: match the terms

memo

Cache
dict

Dictionary
n

Parameter
return

Return
What is Fibonacci memoization's complexity?
- Θ(log n)
- Θ(2^n)
- Θ(n^2)
- Θ(n)
Show answer

Θ(n) — Θ(n).

Next lesson: Dict-based cache

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies