Memoization is a technique of caching expensive function calls and returning the cached result when a same input call happens again. This technique works well with pure functions, which are functions that return the same value when they have the same input and their evaluation has no side-effects.
// Simple Fibonacci const f = n => (n <= 1 ? 1 : f(n - 1) + f(n - 2)); // Memoized Fibonacci const mf = (n, m = ) => m[n] ? m[n] : (m[n] = n <= 1 ? 1 : mf(n - 1, m) + mf(n - 2, m)); // Results console.time("Simple Fibonacci"); f(40); console.timeEnd("Simple Fibonacci"); console.time("Memoized Fibonacci"); mf(1475); console.timeEnd("Memoized Fibonacci");
Running the code above yields the following results:
Simple Fibonacci: 2122.483ms Memoized Fibonacci: 2.855ms
Although the input is massively different (40 vs 1476), there's a 1000x+ speed up on the memoized function over the simple one, which would take an eternity with an input that high...