Recursion And BackTracking - VijayIndia/leetcode GitHub Wiki
Tail End Recursion:
| Tail End Recursion | Non-Tail End Recursion |
|---|---|
| void func(int n){ print(n);//1 func(n-1);//2 } |
void func(int n){ func(n-1);//2 print(n);//1 } |
| Its faster than non-tail end recursion | Its slower than tail end recursion |
| Its Space Complexity is O(1) because only 1 copy is stored | Its Space Complexity is O(n) because it needs to do recursive and then print local copy |
Base Case:
Condition to stop the recursion is called as Base case
| Example | Explanation |
|---|---|
| void func(int n){ if(n==0) return; print(n); func(n-1); } |
In this if(n==0) return; is the base case |
Types of Recursion:
| Problem Type | Recursion Tree | Logic | Code | Related Problems |
|---|---|---|---|---|
| Subset - Small sets within bigSet(bigArray) |  |
i)Do Recursion without adding new Element ii)Do Recursion With adding new Element |
recursion("ABC","",0,new ArrayList());//Initial Caller Function void recursion(String str,String currStr,int index,ArrayList arrList){ if(index==str.length()){ arrList.add(currStr); return; } recursion(arr,currStr,index+1,arrList); recursion(arr,currStr+str.charAt(index),index+1,arrList); } |
Subset Sum |
| Permutation - Serveral Possible variations of array(Reordering) |  |
a)Use a for loop for all variation at that index i)Do Swap at the currentIndex of String ii)Make Recursion call iii)Revert the swap done in 1 to get original string |
private static void recursion(String str,int currIndex){ if(currIndex==str.length()){ arrList.add(str); return; } int j=currIndex; for(int i=currIndex;i<str.length();i++){ str=swap(str,i,j); recursion(str,currIndex+1); str=swap(str,j,i); } } |
Possible words from Phone Digits |
| General Recursion | Doing blind Recursion with all possible combos | void recursion(int remainingLength,int a,int b,int c){ if(remainingLength==0){ return 0; }else if(remainingLength<0){ return -1; } result=max( recursion(n-a,a,b,c), recursion(n-b,a,b,c), recursion(n-c,a,b,c) ); if(result==-1){ return -1; } return 1+result; } |
Rope Cutting Problem | |
| Josephus Problem | Watch GFG Video | i)In every recursion call a element is deleted ii)Also Starting index of the element is changed at every recursion call |
||
| Tower of Hanoi Problem | Watch GFG Video |
Diff Recursion Vs Backtracking :
| Recursion | Backtracking |
|---|---|
| Call all scenarios until it hits basecase | Recursion is stopped at failure scenario, only success scenarios is executed till basecase |
BackTracking:
| Example | Explanation |
|---|---|
| void func(int n){ if(n==0) return; print(n); if(isSafe(n)){ func(n-1); } } |
In this if(isSafe(n)) is the backtracking case |
| Problem Type | Logic | Recursion Tree |
|---|---|---|
| BackTracking | i)Marking the current path as true ii)Do Recursion with the following path iii)If Above recursion returns true, return true else Mark the current path as false(reverting the above change) and return false |
public boolean backTracking(int rowIndex,int colIndex){ if(isSafe(rowIndex,colIndex)){ sol[rowIndex][colIndex]=1;// Marking it as part of Solution if(rowIndex==2 && colIndex==2 && isSafe(rowIndex,colIndex)){ //Reached final Point && Success flow return true; } boolean rowIncrementResult=backTracking(rowIndex+1,colIndex);//Row Increment boolean colIncrementResult; if(!rowIncrementResult){ colIncrementResult=backTracking(rowIndex,colIndex+1);//Column Increment } if(rowIncrementResult or colIncrementResult){ return true; } sol[rowIndex][colIndex]=0; //As this option failed, Reverting this index as part of this solution } return false; // Reached the failure flow } |
| NQueens Problem | i)Fill Column by Column Advantages: a)If logic fails,then only particular column needs to be backtracked or else if implemented differently we would be backtracking for entire matrix b)Advantages are only left columns upper and lower diagonal needs to be checked |
Refer GFG video |