01 Aug 2019

Memoized Fibonacci

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...