Recursion Code Practice
Recursion
--------------------------------------------------------------------------------------------------------------------------
1) Print a string in reverse.
eg) "abcd" -> "dcba"
code:-
import java.util.Scanner;
public class Main
{
public static void printRev(String str, int idx){
if(idx==0){
System.out.println(str.charAt(idx));
return;
}
System.out.print(str.charAt(idx));
printRev(str,idx-1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
printRev(str,str.length()-1);
}
}
Time Complexity = O(n)
Output:-
abcd
dcba
--------------------------------------------------------------------------------------------------------------------------
2) Find the 1st and last accurance of an element in String
eg) "abaacdaefaah" element -> a
Code:-
import java.util.Scanner;
public class Main
{
public static int first = -1;
public static int last = -1;
public static void findOccurance(String str, int idx, char element){
if(idx==str.length()){
System.out.println(first);
System.out.println(last);
return;
}
char currChar = str.charAt(idx);
if(currChar==element){
if(first==-1){
first = idx;
}
else{
last= idx;
}
}
findOccurance(str,idx+1,element);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
char element = sc.next().charAt(0);
findOccurance(str,0,element);
}
}
Output:-
abaacdaefaah
a
0
10
-----------------------------------------------------------------------------------------------------------------------------
3) Check if an array is sorted (strictly increasing) -> { 1,2,3,4,5}
Code:-
public class Main
{
public static boolean isSorted(int arr[], int idx){
if(idx==arr.length-1){
return true;
}
if(arr[idx]<arr[idx+1]){
return isSorted(arr, idx+1);
}
else{
return false;
}
}
public static void main(String[] args) {
int arr[] = {1,2,3,4,5};
System.out.println(isSorted(arr,0));
}
}
Output: - true
--------------------------------------------------------------------------------------------------------------------------
4) Move all 'x' to the end of the string "axbcxxd"
Code:-
public class Main
{
public static void moveAllX(String str, int idx, int count, String newStr){
if(idx==str.length()){
for(int i=0;i<count;i++){
newStr+= 'x';
}
System.out.println(newStr);
return;
}
char currChar = str.charAt(idx);
if(currChar=='x'){
count++;
moveAllX(str,idx+1,count,newStr);
}
else{
newStr+=currChar;
moveAllX(str,idx+1,count,newStr);
}
}
public static void main(String[] args) {
String str = "axbcxxd";
moveAllX(str,0,0,"");
}
}
Output:- abcdxxx
----------------------------------------------------------------------------------------------------------------------------
5) Remove all duplicate in a String.
eg) "abbccda" -> "abcd"
Code:-
public class Main
{
public static boolean[] map = new boolean[26];
public static void removeDuplicate(String str, int idx, String newStr){
if(idx == str.length()){
System.out.println(newStr);
}
char currChar = str.charAt(idx);
if(map[currChar -'a']){
removeDuplicate(str,idx+1,newStr);
}
else{
newStr+= currChar;
map[currChar - 'a']= true;
removeDuplicate(str, idx+1, newStr);
}
}
public static void main(String[] args) {
String str = "abbccda";
removeDuplicate(str,0,"");
}
}
Output:-
abcd
-----------------------------------------------------------------------------------------------------------------------------
6.a) Print all the Sequence of a string
"abc"
Code : -
public class Main
{
public static void subSequence(String str, int idx, String newString){
if(idx==str.length()){
System.out.println(newString);
return;
}
char currChar = str.charAt(idx);
// to be
subSequence(str, idx+1, newString+currChar);
//to not be
subSequence(str,idx+1,newString);
}
public static void main(String[] args) {
String str ="abc";
subSequence(str,0,"");
}
}
OutPut : -
abc
ab
ac
a
bc
b
c
-----------------------------------------------------------------------------------------------------------------------------
6.b) Print all permutations of a String.
eg) "abc"
Code: -
public class Main
{
public static void printPrem(String str, String premutation){
if(str.length()==0){
System.out.println(premutation);
return;
}
for(int i=0;i<str.length();i++){
char currChar = str.charAt(i);
String newStr = str.substring(0,i)+ str.substring(i+1);
printPrem(newStr, premutation+currChar);
}
}
public static void main(String[] args) {
String str = "abc";
printPrem(str,"");
}
}
Output:-
abc
acb
bac
bca
cab
cba
-----------------------------------------------------------------------------------------------------------------------------
7) Print all the subsets of a set of first n natural numbers.
eg) take n =3;
Code: -
import java.util.*;
public class Main
{
public static void printSubset(ArrayList<Integer>subset){
for(int i=0;i<subset.size();i++){
System.out.print(subset.get(i)+" ");
}
System.out.println();
}
public static void findsubSubset(int n, ArrayList<Integer>subset){
if(n==0){
printSubset(subset);
return;
}
//add hoga
subset.add(n);
findsubSubset(n-1,subset);
//add nhi hoga
subset.remove(subset.size()-1);
findsubSubset(n-1,subset);
}
public static void main(String[] args) {
int n =3;
ArrayList<Integer> subset = new ArrayList<>();
findsubSubset(n,subset);
}
}
Output:-
3 2 1
3 2
3 1
3
2 1
2
1
-----------------------------------------------------------------------------------------------------------------------------
8) Find the number of ways in which you can invite n peoples to your party, single or in pairs.
eg.) let n =4
Code: -
import java.util.*;
public class Main
{
public static int callguests(int n){
if(n<=1){
return 1;
}
//Single
int way1 = callguests(n-1);
//pair
int way2 = (n-1)*callguests(n-2);
return way1 + way2;
}
public static void main(String[] args) {
int n =4;
System.out.println(callguests(n));
}
}
Output: - 10
----------------------------------------------------------------------------------------------------------------------------
9) Place Tiles of size (1 x m) in a floor of size (n x m) .
Code:-
public class Main
{
public static int placeTiles(int n, int m){
if(n==m){
return 2;
}
if(n<m){
return 1;
}
//vertically
int vertPlacement = placeTiles(n-m,m);
//horizantal
int horPlacement = placeTiles(n-1,m);
return vertPlacement + horPlacement;
}
public static void main(String[] args) {
int n =4, m=2;
System.out.println(placeTiles(n,m));
}
}
Output :- 5
-----------------------------------------------------------------------------------------------------------------------------
10) Count total paths in a maze to move from (0,0) to (n,m):
eg) n=3,m=3
code:-
public class Main
{
public static int countPaths(int i, int j, int n, int m){
if(i==n|| j==m){
return 0;
}
if(i==n-1 && j==m-1){
return 1;
}
//move downwords
int downPath = countPaths(i+1,j,n,m);
//move rights
int rightPath = countPaths(i,j+1,n,m);
return downPath +rightPath;
}
public static void main(String[] args) {
int n =3, m =3;
System.out.println(countPaths(0,0,n,m));
}
}
Output :- 6
-----------------------------------------------------------------------------------------------------------------------------
11) Tower of Hanoi
public class Main
{
public static void towerofHanoi(int n, String src, String helper, String dist){
if(n==1){
System.out.println("transfer disk "+ n+ " from "+src+" to "+dist);
return;
}
towerofHanoi(n-1,src,dist,helper);
towerofHanoi(n-1,helper,src,dist);
}
public static void main(String[] args) {
int n =3;
towerofHanoi(n,"s","H","D");
}
}
Output : for n=3 => 7
Comments
Post a Comment