Lessons · JavaScript · memoising (not doing it twice)
Remember what you already worked out
When a recursion asks the same smaller question down more than one branch, store each answer the first time. The code barely changes; the cost changes class.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
It is the difference between a function that answers in a blink and one that never finishes, and it is the honest half of 'dynamic programming', which is a grand name for not doing the same work twice.
How to think about it
Write the plain recursion first, because it is easier to get right. Then ask whether any subproblem is reached by more than one route. If it is, wrap it in a Map lookup and change nothing else.
Worked example
let calls = 0;Count the work the plain version does.
function fib(n) { calls++; return n < 2 ? n : fib(n - 1) + fib(n - 2); }fib(n-2) is computed again inside fib(n-1).fib(20);
console.log(calls);21891
const memo = new Map();One line of storage.
let cachedCalls = 0;
function cachedFib(n) {if (memo.has(n)) return memo.get(n);Answered before: hand it back.
cachedCalls++;
const value = n < 2 ? n : cachedFib(n - 1) + cachedFib(n - 2);Identical body.
memo.set(n, value);Store it the first time.
return value;
}
cachedFib(20);
console.log(cachedCalls);21
Your turn
Return the stored answer instead of working it out again.
if (memo.has(n)) return memo.(n);
Solve one with the tests running
The trap
Caching only pays when subproblems OVERLAP. Where every branch is a fresh question the Map fills with misses and buys nothing. A Map keyed by an object also misses every time, because two equal-looking objects are different keys.