This content originally appeared on DEV Community and was authored by Umashankar S
What is Memorization ?
- In a non technical words: Assume, you want to watch one movie, and you downloaded that movie (2TB) and you watched.
After one day, again you want to watch that same movie because its quite interesting. so what you will do now?
Again you will download (2TB) ? or you will watch from your already downloaded file?
In a Technical Words:- It is an optimization technique that speeds up applications by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
Before get into the memorization deeply, lets understood the recursion first.so we will have a better understanding, where we can use our memorization.
Recursion: Recursion is a technique to iterate over the function repeatedly. untill we get a result or untill the condition satisfied.
fibonacci program with recursion:
function fib(n) {
if(n<=2) {
return 1;
}
else {
return fib(n-1)+fib(n-2)
}
}
console.log(fib(40));
In the above code, we are using recursion concept to calculate fibonacci. so fib(n) will be repeated most of the times.
eg:- fib(40) = fib(40-1)+fib(40-2)
fib(39)+fib(38)
And this tree will go further. and lot of fib(4),fib(5), fib(6), fib(n),etc..... series need to calculate.
Assume fib(4), we calculate and we stored it in cache and again if fib(4) came in that tree. we don't need to calculate again. Just we need to return it from the cache. So this will improve the response time as well.
fibonacci program with recursion and memorization:
let previousValue = []
function fib(n) {
if(previousValue[n] != null) { ////memorization
return previousValue[n];
}
if(n<=2) {
return 1;
}
else {
result = fib(n-1)+fib(n-2)
}
previousValue[n] = result //memorization
return result
}
console.log(fib(40))
And you guys can take both the programs and you guys can check that, which one is having a better response time.
Thanks for your time!!
Cheers!!
This content originally appeared on DEV Community and was authored by Umashankar S
Umashankar S | Sciencx (2021-12-29T19:15:36+00:00) Memorization in Recursion (JS). Retrieved from https://www.scien.cx/2021/12/29/memorization-in-recursion-js/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.