Skip to content
dreamcode
dreamcode
← Map
Memoization
Lesson 43 of 48
+15 XP on finish
JS ALGORITHMSChapter 8 · JS Algorithms

Memoization

Memoization stores the result of each call so the same input never gets computed twice. Naive recursive Fibonacci recomputes the same values over and over and its work explodes exponentially; with a cache it becomes linear. A small higher-order memoize function can add caching to any function of one argument.

Worked example

How it reads

  • slowFib(20) makes more than 20,000 calls
  • memoize wraps any function with a cache
  • fastFib calls the memoized version, so every n is computed once
Cloud tip: Memoization only pays off when the same inputs come up again, like overlapping recursive calls.
index.js
JAVASCRIPT
real JavaScript, runs in your browser
Console
Run your code to see its output here.
YOUR TURN

ways(n) counts the ways to climb n stairs 1 or 2 steps at a time. Add a Map cache so it never computes the same n twice, then print ways(60): 2504730781961.

Press Run to check your work.
Practice this →