Session 13: Recursion

Original Session

Date: 28 Nov 2024

Topic: Recursion

1. Concept: Same function calling itself, but for smaller problem.
   1. Same function calling itself, but for smaller problem.
   2. When do we use it ?
      1. Bigger problem with smaller problems to which we know the solution.
      2. Keep on solving smaller problem and bigger problem gets solved.
   3. Two important points
      1. Base Condition
         1. Condition where we have to stop.
      2. Relation / Find Pattern
         1. Pattern is any relationship we need to form.
            
            

2. Concept: Head Recursion vs Tail Recursion
   1. Head Recursion - We go into recursion first then calculate in current function.
   2. Tail Recursion - We calculate in current function then go into recursive function.
      
      

3. Concept: Recursion with Auxilary Space = Memoization, Iteration with Auxilary Space = Tabulation

Programs

1. 509. Fibonacci Number
   1. Leetcode link
      
      

   public int fib(int n) {
           
           if (n <= 1) {
               return n;
           }
   
           return fib(n-1) + fib(n-2);
       }

2. Factorial.
   1. Example,
      1. 5! = 1 * 2 * 3 * 4 * 5
      2. 0! = 1
   2. Factorial
   3. GFG link
      
      

   int fact(int n) {
   	if (n == 0) {
   		return 1;
   	}
   	
   	return n*fact(n-1);
   }

3. Sum of Natural numbers using recursive
   1. 
      
      

   int sum(int n) {
   	if (n == 1) {
   		return 1;
   	}
   	
   	return n + sum(n-1);
   }

4. Power Function
   1. 
      
      

   int power(int value, int power) {
   	
   	if (power == 0) {
   		return 1;
   	}
   	
   	return value*power(value, power-1);
   }

5. Sum of Digits 1963
   1. 
      
      

   int sumDigit(int n) {
   	
   	if (n<=0) {
   		return 0;
   	}
   	
   	return (n%10) + sumDigit(n/10);
   }

6. Print Sum of all Subsets of given set
   1. GFG link
      
      

   public ArrayList<Integer> subsetSums(int[] arr) {
           // code here
           
           ArrayList<Integer> subsetSum = new ArrayList();
           subset(arr, 0, 0, arr.length-1, subsetSum);
           return subsetSum;
       }
       
       void subset(int[] arr, int sum, int l, int r, ArrayList<Integer> subsetSum) {
           
           if (l>r) {
               
               subsetSum.add(sum);
               return;
           }
           
           // include arr[l]
           subset(arr, sum + arr[l], l+1, r, subsetSum);
           
           // exclude arr[l]
           subset(arr, sum, l+1, r,subsetSum);
       }

7. 62. Unique Paths
   1. Leetcode link
      
      

       // Memoization
       Map<String, Integer> map = new HashMap();
       public int uniquePaths(int m, int n) {
           
           if (m == 1 || n == 1) {
               return 1;
           }
   
           String key = m + "," + n;
           if (map.containsKey(key)) return map.get(key);
   
           Integer reuslt = uniquePaths(m, n-1) + uniquePaths(m-1, n);
           map.put(key, reuslt);
   
           return reuslt;
       }

8. 22. Generate Parentheses
   1. Open < N = Add Open bracket, Open > Close = Add Close bracket
   2. Leetcode link

   public List<String> generateParenthesis(int n) {
           
           List<String> ans = new ArrayList();
           parenthesis(ans, n, 0, 0, "");
           return ans;
       }
   
       void parenthesis(List<String> ans, int n, int open, int close, String s) {
   
           if (open == n && close == n) {
               ans.add(s);
               return;
           }
   
           if (open < n) {
               parenthesis(ans, n, open + 1, close, s + "(");
           }
   
           if (open > close) {
               parenthesis(ans, n, open, close + 1, s + ")");
           }
       }