Recursion's Important Questuions

1.  Implement Merge Sort
2.  Suppose you have a string made up of only the letters 'a' and 'b'. Write a recursive function that checks if the string was generated using the following rules:
 a)  the string begins with an 'a'
 b)  each 'a' is followed by nothing or an 'a' or "bb"  c)  each "bb" is followed by nothing or an 'a’

3.  Reverse a string using recursion 

4.  Return all subsets of an array
5.  Count number of ways for a child to take n steps if she can take 1,2 or 3 steps at a time.
6.  Using the phone keypad return all possible words that can be produced given input digits.
     e.g. 23 -> “ad, ae, af, bd, be, bf, cd, ce, cf”
 a)  Instead of returning print all these 

Soln:-

Merge Sort

#include<iostream>

using namespace std;

int temp[1000];

void merge(int a[],int startIndex,int endIndex){

int mid=(startIndex+endIndex)/2;

int i,j,k;

i=startIndex;j=mid+1;k=0;

while(i<=mid&&j<=endIndex){

if(a[i]<a[j]){

temp[k]=a[i];  i++;k++;

}

else{

temp[k]=a[j];   j++;k++;

}

}

while(i<=mid){

temp[k]=a[i];     i++;k++;

}

while(j<=endIndex){

temp[k]=a[j];      j++;k++;

}

}

void mergesort(int a[],int startIndex,int endIndex){

if(startIndex<endIndex){

int mid=(startIndex + endIndex)/2;

mergesort(a,startIndex,mid);

mergesort(a,mid+1,endIndex);

merge(a,startIndex,endIndex);

}

}

main(){

int arr[100], n;

cin >> n;

for (int i = 0 ; i < n; i++) {

cin >> arr[i];

}

mergesort(arr,0,n-1);

cout <<"\n";

for (int i = 0 ; i < n; i++) {

cout << temp[i]<<"\t";

}

}

2.  Suppose you have a string made up of only the letters 'a' and 'b'. Write a recursive function that checks if the string was generated using the following rules: 

 a)  the string begins with an 'a'
 b)  each 'a' is followed by nothing or an 'a' or "bb"  c)  each "bb" is followed by nothing or an 'a’

#include<iostream>

#include<stdio.h>

using namespace std;

int checkstring(char *t){

if(*t==NULL){

return 1;

}

char *c=t;

if(*t=='a'){

if(*(c+1)=='a'){

return checkstring(t+1);

}

else if(*(c+1)=='b'){

return checkstring(t+1);

}

if(*(c+1)==NULL){

return 1;

}

else{

return 0;

}

}

else if(*t=='b'){

if(*(c+1)=='b'&&*(c+2)=='a'){

return checkstring(t+2);

}

else if(*(c+1)=='b'&&*(c+2)==NULL){

return 1;

}

else{

return 0;

}

}

}

main(){

char s[100];

cin>>s;

char *t;

t=s;

if(*t=='a'){

t=t++;

if(checkstring(t)){

cout<<"valid substring";

}

else{

cout<<"Not a valid substring";

}

}

else{

cout<<"Not a valid substring";

}

}

3.  Reverse a string using recursion 

#include<iostream>

#include<stdio.h>

using namespace std;

void reversePrint(char *t){

if(*t==NULL){

return;

}

reversePrint(t+1);

cout<<*t;

}

main(){

char s[100],*t;

cin>>s;

t=s;

reversePrint(t);

}

4.  Return all subsets of an array 

Method 1

#include<iostream>

using namespace std;

void subset(int arr[],int temp[],int index,int subindex,int len){

if(index==len){

if(subindex==-1){

cout << "{ }";

}

else{

cout << "{ ";

for(int i=0;i<=subindex;i++){

cout << temp[i] << ", ";

}

cout<<" }\n";

}

return;

}

temp[subindex+1]=arr[index];

subset(arr,temp,index+1,subindex+1,len);

subset(arr,temp,index+1,subindex,len);

}

main(){

int n;

int arr[100],temp[100];

cin >> n;

for (int i = 0; i < n ; i++) {

cin >> arr[i];

}

subset(arr,temp,0,-1,n);

}

method 2

#include<iostream>

using namespace std;

int print_subset(int arr[], int subset[1000][100], int index, int len){

if(index==len){

subset[0][0]=-1;

return 1;

}

int x= print_subset(arr,subset,index+1,len);

for(int i=0;i<x;i++){

int j=0;

for(;subset[i][j]!=-1;j++){

subset[x+i][j]=subset[i][j];

}

subset[x+i][j]=arr[index];

subset[x+i][j+1]=-1;

}

return 2*x;

}

main(){

int n;

int arr[100], subset[1000][100];

cin >> n;

for (int i = 0; i < n ; i++) {

cin >> arr[i];

}

int total_subsets = print_subset(arr, subset, 0, n);

for(int i = 0 ; i < total_subsets; i++) {

cout << '{';

for(int j=0; subset[i][j]!= -1; j++) {

cout << subset[i][j] << ',';

}

cout << '}' << endl;

}

return 0;

}

5.  Count number of ways for a child to take n steps if she can take 1,2 or 3 steps at a time.  

#include<iostream>

#include<stdio.h>

using namespace std;

int steps(int n){

if(n==1){

return 1;

}

else if(n==2){

return 3;

}

else if(n==3){

return 4;

}

else{

return steps(n-1)+steps(n-2)+steps(n-3);

}

}

main(){

int n;        

cin >> n;           //Enter no of spaces

int total=steps(n);

cout<<"\nNo of ways to climb "<<n<<" steps = "<<total;

}