Memoization is a term coined by Donald Michie in 1968, which is derived from the Latin word «memorandum» (to be remembered). In the context of software development, memoization is a technique that saves the results of executing functions to avoid recalculations.
It’s quite simple: before calling a function, it first checks if there was the same function with the same arguments called before. If yes, then the stored result is returned, otherwise, the answer is calculated. The result is then stored and returned.
In this article, we will use memoization to find Fibonacci numbers.
Let me remind you that the Fibonacci sequence is defined so that each number is the sum of the two previous numbers. For instance, the first 6 terms of the Fibonacci sequence are 1, 1, 2, 3, 5, 8.
First, let's define a recursion function that we can use to display the first n numbers in the Fibonacci sequence:
const fib = (n) => {
if (n === 1) {
return 1;
}
if (n === 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
In the example above, we describe the beginning of the sequence - if the input value is 1 or 2, then the function returns 1. If the input value is greater than 2, the results of recursion function calls are returned, summing the previous two Fibonacci numbers.
Now let's print the first 10 numbers:
for (let i = 1; i < 11; i++) {
console.log(`fib(${i}) = ${fib(i)}`);
}
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
Seems like it works just fine. Now let's try to display the first 40 numbers of the sequence:
for (let i = 1; i < 41; i++) {
console.log(`fib(${i}) = ${fib(i)}`);
}
...
fib(30) = 832040
fib(31) = 1346269
fib(32) = 2178309
fib(33) = 3524578
fib(34) = 5702887
fib(35) = 9227465
fib(36) = 14930352
fib(37) = 24157817
fib(38) = 39088169
fib(39) = 63245986
fib(40) = 102334155
Have you noticed it? — Calculations take much more time than for the first 10 numbers from the first example. This is because, with each subsequent calculation, we repeat the same work.
Basically, a recursion approach to solving this kind of problem is considered bad practice due to the high time complexity of the algorithm. In this case, this solution is O(log N). When calculating a sequence for large numbers, this algorithm is inefficient.
Now let’s see how the recursion function calculates each number:
fib(1) = 1
fib(2) = 1
fib(3) = fib(1) + fib(2) = 2
fib(4) = fib(3) + fib(2) = 3
fib(5) = fib(4) + fib(3) = 5
fib(6) = fib(5) + fib(4) = 8
Here is the visual representation of it:
Note that for fib(6) we repeat the calculation of fib(4) , fib(3) and fib(2). If we had a way to remember/save these values after they have been computed, we could avoid repetition. This creates motivation for the memoization method.
Now let's go over the implementation steps of the memoization method. Let's initialize the object that will store the cache:
const cached = {};
Next, we need to define our memoization function. First, we check if the sequence number exists in the cache. If the number is there, then return the number corresponding to the number:
const memoFib = (n) => {
if (n in cached) {
return cached[n];
}
...
}
Next, we determine the two initial numbers of the sequence. If the function argument is 1 or 2, we should set the value to 1:
const memoFib = (n) => {
...
if (n === 1) {
return 1;
}
if (n === 2) {
return 1;
}
...
}
Next, let’s consider the recursive cases. If the argument is greater than 2, we need to set the value to the sum of the previous two numbers:
const memoFib = (n) => {
...
const calculated = memoFib(n - 1) + memoFib(n - 2);
...
}
Finally, we save the value in our cache and return the value:
const memoFib = (n) => {
...
cached[n]= calculated;
return calculated;
}
This is what the complete function looks like:
const cached = {};
const memoFib = (n) => {
if (n in cached) {
return cached[n];
}
if (n === 1) {
return 1;
}
if (n === 2) {
return 1;
}
const calculated = memoFib(n - 1) + memoFib(n - 2);
cached[n] = calculated;
return calculated;
}
Now, let's try to get the first 40 Fibonacci numbers with our new function:
for (let i = 1; i < 41; i++) {
console.log(`memoFib(${i}) = ${memoFib(i)}`);
}
There is a more general way to memoize is to implement a function to create a memoized function. It's quite simple:
const memo = (fn) {
const cache = {};
const slice = Array.prototype.slice;
return function () {
const args = slice.call(arguments);
const key = JSON.stringify(args);
if (cache[key]) {
return cache[key];
}
const result = fn.apply(null, args);
cache[key] = result;
return result;
};
}
Using the memo function, we can achieve the same speed as our memoFib function:
const memoFibV2 = memo((n) => {
if (n === 1) {
return 1;
}
if (n === 2) {
return 1;
}
return memoFibV2 (n - 1) + memoFibV2 (n - 2);
});
for (let i = 1; i < 41; i++) {
console.log(`memoFibV2(${i}) = ${memoFibV2(i)}`);
}
Where can this be applied? You can use it in cases where you need to perform complex and lengthy calculations.
Conclusion
In this article, we have reviewed the memoization method in JavaScript.
First, it is shown how the unsophisticated implementation of the recursion function causes very slow calculations of a large number of numbers in the Fibonacci sequence.
We then defined a new method in which we store the previous values already computed in the cache, which results in a significant speedup of calculations.
Next, we discussed the memo function, which showed similar results to our memoFib function.
I hope you found this article useful and exciting to read. Thank you for your time!