Memoization in Recursion (JS)

What is Memoization ?

• 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 memoization deeply, lets understood the recursion first.so we will have a better understanding, where we can use our memoization.

---

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 memoization:

let previousValue = []
function fib(n) {
  if(previousValue[n] != null) { //memoization
    return previousValue[n];
  }
  if(n<=2) {
    return 1;
  }
  else {
    result =  fib(n-1)+fib(n-2)
  }
  previousValue[n] = result  //memoization
  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!!

Comments

[Umashankar S]

ohh sry. spelling mistake, recorrected .

Thank you..