Day 77: Memoization Magic – Speeding Up Recursion with Maps
Ever write a recursive function that works… but takes forever to run on big inputs? You’re not alone. That’s where memoization comes in. It’s like giving your function a short-term memory—so it doesn’t redo work it already did.
What is Memoization? Memoization is a technique to cache the results of expensive function calls and return the cached result when the same inputs occur again. You save time by not recalculating the same subproblem over and over.
Classic Example: Fibonacci (Without Memoization) js CopyEdit function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } This has exponential time complexity: O(2ⁿ)
With Memoization Using Map js CopyEdit function fib(n, memo = new Map()) { if (memo.has(n)) return memo.get(n); if (n <= 1) return n; const result = fib(n - 1, memo) + fib(n - 2, memo); memo.set(n, result); return result; }
Time complexity now is O(n) The Map acts as a fast-access memory
When to Use It Recursive solutions with overlapping subproblems Dynamic Programming (especially top-down)
Problems like: Climbing Stairs, Coin Change, Edit Distance TL;DR Memoization = Smart caching Map = Your function’s memory card Next time recursion’s dragging you down, wrap it with a Map and feel the speed.
100daysofcode lebanon-mug
