Just little basic about recursion dynamic programming and memorization using some simple example in javascript

working sample
https://stackblitz.com/edit/js-h3abpu


recursion  and memorization these three are the 2 important pillar of computer programming when you are dealing with big task and you want to break your task to smaller parts.

let take a example a simple example

you have a array and you want to find to maximum value form that array.

so let try to solve this problem using recursion

//Find a maximum value in a unsorted array

//here how i can find max item from a array using recursion

function findMax(arr,len)

{

//if length is 1 return first item

if(len==1)

{

return arr[0];

}

//else recursively search the next maximum item in the array

return Math.max(arr[len-1],findMax(arr,len-1))

}

  now find the minimum item in array

function findMin(arr,len=arr.length)

{

if(len==1)

{

return arr[0];

}

return Math.min(arr[len-1],findMin(arr,len-1))

}

time complexity for above two programm is O(n) because which is equivalent to a loop so no performance lack

let take some more example=>

simple example of fibonacci series

//fibonacci series with recursion with memorization

function fib(n)

{

if(n<=1)

{

return n;

}

return fib(n-1)+fib(n-2);

}

check out time time complexity of above example

https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/

getting maximum and minimum from a array does not require memorization because result is different in every iteration but there we are breaking our problem in two 2 subproblem and so on
please check the below video for more information

https://www.youtube.com/watch?v=5dRGRueKU3M&t=327s


now with memorization we can remember the result and solve this problem in O(n)

example

//with memorization---------------------------------------------------------

var arr=[];

function fibM(n)

{

if(n<=1)

{

return n;

}

if(arr[n])

{

return arr[n];

}

arr[n]=fibM(n-1)+fibM(n-2);

return arr[n];

}

console.log("--->>>>>",fibM(5));

finding a string is palindrome or not is another good example of recursion

function isPalindrome(str,start=0,end=str.length-1)

{

if(start==end)

{

return true;

}

if(str[start]!=str[end])

{

return false;

}

if(start<end)

{

return isPalindrome(str,++start,--end);

}

return true

}

console.log(isPalindrome("geeksskeeg"));

now lets try to solve one more problem which is LCS (longest common subsequence) you can find a great video on it

here

https://www.youtube.com/watch?v=sSno9rV8Rhg&t=605s

without memorization

//Longest Common Subsequence | Introduction & LCS Length

//using recursion

//get two string first

let str1="ABCBDAB";

//get second string

let str2="BDCABA";

var counter=0;

function findLongest(str1,str2,len1=str1.length,len2=str2.length)

{

//console.log(counter++)

//if one of two string is empty so it would be zero length return it

if(len1==0 || len2==0)

{

return 0;

}

//if letter matched in string move to next char with +1

if(str1[len1-1]==str2[len2-1])

{

return findLongest(str1,str2,len1-1,len2-1)+1;

}

//compare the two string and return the maximum between two string

return Math.max(findLongest(str1,str2,len1,len2-1),findLongest(str1,str2,len1-1,len2))

}

console.log("with recursion",findLongest(str1,str2));


with memorization

/but this algo is not works in real life check out how many times counter is excuted its

//now here comes the memorization

//memorization is a very simple techique the remember the result which occur again and again

//check out the Longest of two string and fill the string with it

let len=str1.length>str2.length?str1.length:str2.length;

let tempArray=Array(len).fill([]);

function findLongestWithM(str1,str2,i=len,j=str2.length)

{

let finalResult;

//if i or j is equal to zero return

if(i==0 || j==0)

{

finalResult= 0;

}

//check if char matched in string store the result and move by 1

else if(str1[i-1]==str2[j-1])

{

finalResult=findLongestWithM(str1,str2,--i,--j)+1;

}

else

{

//get the maximum of two

finalResult=Math.max(findLongestWithM(str1,str2,i,--j),findLongestWithM(str1,str2,--i,j))

}

return finalResult;

}

console.log("with recursion and memorization",findLongestWithM(str1,str2));