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, is a technique that saves the results of executing functions to avoid recalculations. memoization 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 numbers in the Fibonacci sequence: n 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 we repeat the calculation of , and . If we had a way to these values after they have been computed, we could avoid repetition. This creates motivation for the . fib(6) fib(4) fib(3) fib(2) remember/save 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 . First, we check if the sequence number exists in the cache. If the number is there, then return the number corresponding to the number: memoization function 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 function, we can achieve the same speed as our function: memo memoFib 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 in JavaScript. memoization method , 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. First We defined a new method in which we store the previous values ​​already computed in the cache, which results in a significant speedup of calculations. then , we discussed the function, which showed similar results to our function. Next memo memoFib I hope you found this article useful and exciting to read. Thank you for your time!

Optimizing Performance With Throttling in JavaScript

How Memoization Can Help You Boost Your Javascript Code

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Eliminating Event Storms With Debouncing in JavaScript

Even Fibonacci numbers (Python vs. JavaScript)

How The Yak Tack Algorithm Helps You Remember Words

How to get a performance boost using WebAssembly

Parallel Merge Sort with Fork/Join Framework

Eliminating Event Storms With Debouncing in JavaScript

Even Fibonacci numbers (Python vs. JavaScript)

How The Yak Tack Algorithm Helps You Remember Words

How to get a performance boost using WebAssembly

Parallel Merge Sort with Fork/Join Framework

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps