Recursion One Shot - Advanced Level Questions | Placement (Tech)

Recursion in Java-DSA

Recursion is a programming technique where a function calls itself repeatedly until a certain condition is met. In Java, recursion is commonly used in Data Structures and Algorithms (DSA) to solve problems involving trees, graphs, and other recursive structures.

Here is an example of a recursive function to calculate the factorial of a number:

Here is an example of a recursive function to calculate the factorial of a number:

java
public static int factorial(int n) {
if (n == 0){ 
return 1; 
 } 
else{ 
return n * factorial(n-1);
 } 
}

This function takes an integer n as input and returns the factorial of n. The factorial of a number is the product of all integers from 1 to that number. For example, the factorial of 4 is 4 * 3 * 2 * 1 = 24.

The function first checks if n is equal to 0. If it is, it returns 1 (the base case). If n is not equal to 0, it calls itself with n-1 as the input and multiplies the result with n.

It's important to note that recursive functions can be resource-intensive and can cause a stack overflow error if the recursion depth is too deep. Therefore, it's important to design recursive algorithms carefully and consider alternative approaches when necessary.

ADVANCED

Q1. Print all the permutations of a string.

public class Recursion3 {

 

   public static void printPermutation(String str, int idx, String perm) {

       if(str.length() == 0) {

           System.out.println(perm);

           return;

       }

      

       for(int i=0; i<str.length(); i++) {

           char currChar = str.charAt(i);

           String newStr = str.substring(0, i) + str.substring(i+1);

           printPermutation(newStr, idx+1, perm+currChar);

       }

   }

   public static void main(String args[]) {

       String str = "abc";

       printPermutation(str, 0, "");

   }

}

 

Time complexity - O(n*n!)

Q2. CountPathMaze 

public class Recursion3 {

 

   public static int countPaths(int i, int j, int m, int n) {

       if(i == m-1 || j == n-1) {

           return 1;

       }

 

       return countPaths(i+1, j, m, n) + countPaths(i, j+1, m, n);

   }

 

   public static void main(String args[]) {

       int m = 4, n = 5;

       System.out.println(countPaths(0, 0, m, n));

   }

}

 

Time complexity - O(2^(m+n))

Q3. Tiling problem

public class Recursion3 {

 

   public static int placeTiles(int n, int m) {

       if(n < m) {

           return 1;

       } else if(n == m) {

           return 2;

       }

 

       return placeTiles(n-1, m) + placeTiles(n-m, m);

   }

 

   public static void main(String args[]) {

       int n = 4, m = 4;

       System.out.println(placeTiles(n, m));

   }

}

 

Q4. Friends pairing problem

public class Recursion3 {

 

   public static int pairFriends(int n) {

      if(n <= 1) {

          return 1;

      }

 

       return pairFriends(n-1) + (n-1) * pairFriends(n-2);

   }

 

   public static void main(String args[]) {

       int n = 3;

       System.out.println(pairFriends(n));

   }

}

 

Q5. Subsets of a set

import java.util.ArrayList;

 

public class Recursion3 {

 

   public static void printSubsets(ArrayList<Integer> subset) {

       for(int i=0; i<subset.size(); i++) {

           System.out.print(subset.get(i)+" ");

       }

       System.out.println();

   }

 

   public static void findSubsets(int n, ArrayList<Integer> subset) {

       if(n == 0) {

           printSubsets(subset);

           return;

       }

 

       findSubsets(n-1, subset);

       subset.add(n);

       findSubsets(n-1, subset);

       subset.remove(subset.size() - 1);

   }

 

   public static void main(String args[]) {

       int n = 3;

       findSubsets(n, new ArrayList<Integer> ());

   }

}