Session 12: Revision Session.

Original Session

Date: 23 Nov 2024

Topic: Recursion

1. Concept: Tail Recursion

2. Concept: Head Recursion

1. Printing Name n times using Recurssion

   void printName(String name, int n) {
   	
   	if (n <= 0) {
   		return;
   	}
   	System.out.println(name);
   	printName(name, --n);
   }

2. Print number 1 to N using Recursion

   static void printNumber(int N) {
           printNumber(1, N);
       }
       
       static void printNumber(int count, int N) {
           if (count > N) {
               return;
           }
           System.out.println(count);
           printNumber(++count, N);
       }

3. Print N to 1
   1. 
      
      

   static void printNumber(int N) {
           if (N <= 0) {
               return;
           }
           System.out.println(N);
           printNumber(--N);
       }

4. reverse array with recurssion
   1. 
      
      

   void reverseArray(int[] arr, int left, int right) {
           
           if (left >= right) {
               return;
           }
           
           int swap = arr[left];
           arr[left] = arr[right];
           arr[right] = swap;
           
           reverseArray(arr, ++left, --right);
       }

5. if string is palindrome using recursion
   1. Tail recursion

      boolean isPalindrome(char[] arr, int left, int right) {
              
              if (left >= right) {
                  return true;
              }
              
              if (arr[left] != arr[right]) {
                  return false;
              }
              
      				return isPalindrome(arr, ++left, --right);
          }

   2. Head recursion

   boolean isPalindrome(char[] arr, int left, int right) {
           
           if (left < right) {
               return isPalindrome(arr, ++left, --right);
           }
           
           if (arr[left] != arr[right]) {
               return false;
           }
           
           return true;
       }

6. Nth fibbonacci recursive
   1. 
      
      

   static int fibbonacci(int N) {
           
           if (N <= 0) {
               return 0;
           }
           
           if (N==1) {
               return 1;
           }
           
           int fib = fibbonacci(N-1) + fibbonacci(N-2);
           
           return fib;
       }

7. bubble sort recursive
   1. 
      
      

   static void sort(int[] arr) {
           
           bubbleSort(arr, arr.length);
       }
       
       static void bubbleSort(int[] arr, int N) {
           
           if( N == 1) {
               return;
           }
           
           for (int i=0; i<N-1; i++) {
               if (arr[i] > arr[i+1]) {
                   int swap = arr[i];
                   arr[i] = arr[i+1];
                   arr[i+1] = swap;
               }
           }
           
           bubbleSort(arr, N-1);
       }

8. Print all subsequence
   1. GFG link
   2. explanation here
      
      

   public List<List<Integer>> subsets(int[] nums) {
           List<List<Integer>> ans = new ArrayList<>();
           List<Integer> temp = new ArrayList<>();
           help(ans, temp, nums, 0);
           return ans;
       } 
       
       private void help(List<List<Integer>> ans, List<Integer> temp, int[] nums, int i) {
           // Base case
           if (i >= nums.length) {
               ans.add(new ArrayList<>(temp)); // Add a copy of temp
               return;
           }
   
           // Option 1: Exclude nums[i]
           help(ans, temp, nums, i + 1);
   
           // Option 2: Include nums[i]
           temp.add(nums[i]);
           help(ans, temp, nums, i + 1);
   
           // Backtrack
           temp.remove(temp.size() - 1);
       }