Caching function results
Day 110 of 149
👉 Full deep-dive with code examples
The Math Homework Analogy
Imagine doing math homework:
- Problem 1: What's 7 × 8? You calculate: 56
- Problem 5: What's 7 × 8? You calculate again: 56
- Problem 12: What's 7 × 8? You calculate again: 56
That's wasted effort! If you wrote down "7 × 8 = 56" the first time, you'd just look it up!
Memoization is writing down answers so you don't recalculate them!
The Problem It Solves
Some calculations repeat many times:
- Computing the same thing over and over
- Especially in recursive functions
- Each repeat wastes time
Without saving answers:
- Same work done hundreds of times
- Programs run very slowly
- Your computer struggles unnecessarily
How It Works
Simple three-step process:
- Check → Have I solved this before?
- If yes → Return the saved answer
- If no → Calculate, save it, then return
Think of it like a notepad:
- Before calculating, check your notes
- After calculating, write it down
- Next time, just look it up!
A Classic Example: Fibonacci
Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13...
Each number is the sum of the two before it.
Without memoization:
fib(5) calls fib(4) and fib(3)
fib(4) calls fib(3) and fib(2)
fib(3) gets calculated TWICE!
For fib(50): billions of redundant calculations!
With memoization:
fib(3) calculated once, saved
Next time fib(3) is needed: instant lookup!
For fib(50): around 50 distinct calculations (then lots of lookups).
Where It's Used
- Fibonacci and similar sequences
- Finding shortest paths
- Game AI (chess move evaluation)
- Any problem with repeating subproblems
In One Sentence
Memoization saves the results of expensive calculations so you usually avoid solving the same subproblem over and over.
🔗 Enjoying these? Follow for daily ELI5 explanations!
Making complex tech concepts simple, one day at a time.
Top comments (0)