Skip to main content

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));



















































Comments

Post a Comment

Popular posts from this blog

Creating a word Scramble game where you can drag and drop the word and create a complete word. (drag and drop word Scramble game).

Creating a word game using  phaser game engine which is a javascript based gaming engine  where u can drag and drop world like Word Scramble Game and complete a given word. your index.html file look like below < html > < head > < script src = "src/phaser.min.js" ></ script > < script src = "src/wordGame.js" ></ script > < script src = "src/main.js" ></ script > </ head > < body > </ body > </ html > 1.    <script src="src/phaser.min.js"></script> required to run the  phaser game engine. 2. rest of the two files deals with game logics      <script src="src/wordGame.js"></script>       <script src="src/main.js"></script> you can download whole project from https://github.com/manishchauhan/wordgame/tree/master just copy and paste the project in your local server and run ...
Post a Comment
Read more

starting with three.js and react with a very simple example

 1. three.js is undoubtedly the best library to create interactive content for the web in 3d. link https://threejs.org/ a working sample of three with react can be found below https://stackblitz.com/edit/react-7n5qf9?file=src%2FApp.js why choose threejs 1. lightweight  2.fast 3.big community  https://discourse.threejs.org/ 4. even you can use unity or unreal to publish html5 content but i don't think that would be acceptable in many cases. 5. open-source project. i created a running sample with React  https://stackblitz.com/edit/react-7n5qf9?file=src%2FApp.js
Post a Comment
Read more

A simple binary search tree with generic approach tree can store any type of data. (DFS and BFS)

 1. a binary search tree in c++ using a generic approach with both BFS and DFS approach    working tree    https://www.onlinegdb.com/edit/HkuQLdA-w code=> some properties of binary search tree-> 1. binary search tree is not always a balanced tree.  2. Inorder, traversing gives you sorted data.  3.  best is o(log n) and worst is O(n).  4. left node data is always less than root data and right node data always be greater than root data.  5. red-black tree STL map is a balanced binary search tree. *******************************************************************************/ #include <stdio.h> #include<iostream> #include<queue> using namespace std; template < typename T > class Node {   //can store any type of data private:   //genric data or store any type of data   T data;   //reference of left pointer   Node *left = nullptr;   //reference of right pointer   Node *rig...
Post a Comment
Read more