Skip to main content

Recursion Class 2 | Recursion in One Shot | 9 Best Problems

Recursion Class 2 :-

Recursion is a powerful programming technique that is used in many algorithms and data structures. In Java, recursion is implemented using methods that call themselves.


Tower of Hanoi:

The Tower of Hanoi is a mathematical puzzle that consists of three rods and a number of disks of different sizes, which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

Q1. Tower of Hanoi - Transfer n disks from source to destination over 3 towers.

public class Recursion2 {
public static void towerOfHanoi(int n, String src, String helper, String dest) {
if(n == 1) {
System.out.println("transfer disk " + n + " from " + src + " to " + dest);
return;
}
//transfer top n-1 from src to helper using dest as 'helper'
towerOfHanoi(n-1, src, dest, helper);
//transfer nth from src to dest
System.out.println("transfer disk " + n + " from " + src + " to " + helper);
//transfer n-1 from helper to dest using src as 'helper'
towerOfHanoi(n-1, helper, src, dest);
}
public static void main(String args[]) {
int n = 4;
towerOfHanoi(n, "A", "B", "C");
}
}


Q2. Print a string in reverse.

public class Recursion2 {
public static String revString(String str) {
if(str.length() == 1) {
return str;
}
char currChar = str.charAt(0);
String nextString = revString(str.substring(1));
return nextString + currChar;
}
public static void main(String args[]) {
String str = "abcd";
String reversed = revString(str);
System.out.println(reversed);
}
}


Q3. Find the occurrence of the first and last occurrence of an element using recursion.

public class Recursion2 {
public static int first = -1;
public static int last = -1;
public static void getIndices(String str, char el, int idx) {
if(idx == str.length()) {
return;
}
if(str.charAt(idx) == el) {
if(first == -1) {
first = idx;
} else {
last = idx;
}
}
getIndices(str, el, idx+1);
}
public static void main(String args[]) {
String str = "tabcdfghijakkk";
char el = 'a';
getIndices(str, el, 0);
System.out.println("First occurence : " + first);
System.out.println("Last occurence : " + last);
}
}


Q4. Check if an array is sorted (strictly increasing). - O(n)

public class Recursion2 {
public static boolean checkIfIncreasing(int arr[], int idx) {
if(idx == arr.length-1) {
return true;
}
if(!checkIfIncreasing(arr, idx+1)) {
return false;
}
return arr[idx] < arr[idx + 1];
}
public static void main(String args[]) {
int arr1[] = {1, 2, 3, 4, 5};
int arr2[] = {1, 6, 3, 4, 5};
if(checkIfIncreasing(arr2, 0)) {
System.out.println("Strictly Increasing");
} else {
System.out.println("NOT Strictly Increasing");
}
}
}


Q5. Move all ‘x’ to the end of the string. - O(n)

public class Recursion2 {
//to add all 'x' to the end of the string
public static String addX(int count) {
String newStr = "x";
for(int i=1;i<count; i++) {
newStr += 'x';
}
return newStr;
}
public static String moveAllX(String str, int idx, int count) {
if(idx == str.length()) {
return addX(count);
}
if(str.charAt(idx) == 'x') {
return moveAllX(str, idx+1, count+1);
} else {
String nextStr = moveAllX(str, idx+1, count);
return str.charAt(idx) + nextStr;
}
}
public static void main(String args[]) {
String str = "abcdefxghxixjxxxk";
int count = 0;
String newStr = moveAllX(str, 0, count);
System.out.println(newStr);
}
}


Q6. Remove duplicates in a string.

public class Recursion2 {
public static String removeDuplicates(String str, int idx, boolean present[]) {
if(idx == str.length()) {
return "";
}
char curr = str.charAt(idx);
if(present[curr-'a']) {
return removeDuplicates(str, idx+1, present);
} else {
present[curr-'a'] = true;
return curr + removeDuplicates(str, idx+1, present);
}
}
public static void main(String args[]) {
String str = "abcadbcefghabi";
boolean present[] = new boolean[str.length()];
System.out.println(removeDuplicates(str, 0, present));
}
}


Q7. Print all the subsequences of a string.

public class Recursion2 {
public static void printSubseq(String str, int idx, String res) {
if(idx == str.length()) {
System.out.println(res);
return;
}
//choose
printSubseq(str, idx+1, res+str.charAt(idx));
//don't choose
printSubseq(str, idx+1, res);
}
public static void main(String args[]) {
String str1 = "abc";
String str2 = "aaa";
printSubseq(str1, 0, "");
}
}
Time complexity - O(2^n)


Q8. Print all unique subsequences of a string.

import java.util.HashSet;
public class Recursion2 {
public static void printSubseq(String str, int idx, String res, HashSet<String>
allSubseq) {
if(idx == str.length()) {
if(allSubseq.contains(res)) {
return;
}
allSubseq.add(res);
System.out.println(res);
return;
}
//choose
printSubseq(str, idx+1, res+str.charAt(idx), allSubseq);
//don't choose
printSubseq(str, idx+1, res, allSubseq);
}
public static void main(String args[]) {
String str1 = "abc";
String str2 = "aaa";
HashSet<String> allSubseq = new HashSet<>();
printSubseq(str2, 0, "", allSubseq);
}
}


Q9. Print keypad combination

( 0 -> .;
1 -> abc
2 -> def
3 -> ghi
4 -> jkl
5 -> mno
6 -> pqrs
7 -> tu
8 -> vwx
9 -> yz
)
import java.util.HashSet;
public class Recursion2 {
public static String keypad[] = {".", "abc", "def", "ghi", "jkl", "mno", "pqrs",
"tu", "vwx", "yz"};
public static void printKeypadCombination(String number, int idx, String res) {
if(idx == number.length()) {
System.out.println(res);
return;
}
for(int i=0; i<keypad[number.charAt(idx)-'0'].length(); i++) {
char curr = keypad[number.charAt(idx)-'0'].charAt(i);
printKeypadCombination(number, idx+1, res+curr);
}
}
public static void main(String args[]) {
String number = "23";
printKeypadCombination(number, 0, ""); 

Comments

Popular posts from this blog

Conditional Statements | if, If-else, "if" and "if else", Switch Break | Complete Java Placement Course | Lecture 3

                                    Java - Introduction to Programming Lecture 3 Conditional Statements Conditional statements are a fundamental concept in programming. They are used to make decisions based on certain conditions, allowing the program to perform different actions depending on the input or data it receives. In this article, we'll take a closer look at conditional statements in programming and how they can be used effectively. What are conditional statements? Conditional statements, also known as "if-then" statements, are used in programming to execute certain code if a condition is met. In other words, the program will perform a particular action if a particular condition is true. For example, a program may check if a user has ent...

Recursion in One Shot | Theory + Question Practice + Code | Level 1 - Easy

JAVA Recursion Class 1 (Codes) Q1. Print numbers from 5 to 1. public static void printNumbers(int n) { if(n == 0) { return; } System.out.println(n); printNumbers(n-1); } Q2. Print numbers from 1 to 5. public static void printNumbers(int n) { if(n == 6) { return; } System.out.println(n); printNumbers(n+1); } Q3. Print the sum of first n natural numbers. class Recursion1 { public static void printSum(int n, int sum) { if(n == 0) { System.out.println(sum); return; } sum += n; printSum(n-1, sum); } public static void main(String args[]) { printSum(5, 0); } } Q4. Print factorial of a number n. class Recursion1 { public static void printFactorial(int n, int fact) { if(n == 0) { System.out.println(fact); return; } fact *= n; printFactorial(n-1, fact); } public static void main(String args[]) { printFactorial(5, 1); } } Q5. Print the fibonacci sequence till nth term. class Recursion1 { public static void printFactorial(int a, int b, int n) { if(n == 0) { return; } System.out.println(a); printF...

Java - Introduction to Programming| OOPS concept

  Java - Introduction to Programming Lecture 1 Installation & First Program Install Java a. Install JDK ( https://www.oracle.com/in/java/technologies/javase-downloads.html ) b. Install IntelliJ ( https://www.jetbrains.com/idea/download/#section=mac ) OR b. Install Visual Studio Code (VS Code) - Prefer THIS ( https://code.visualstudio.com/download ) Sample Code Functions A function is a block of code which takes some input, performs some operations and returns some output.  The functions stored inside classes are called methods. The function we have used is called main. Class A class is a group of objects which have common properties. A class can have some properties and functions (called methods). The class we have used is Main. Our 1st Program public class Main {     public static void main (String[] args) {    // Our 1st Program         System. out .println( "Hello World" ) ;     } }   ...