### Recursions are fun

You may like to try out some simple problems to practice recursions. Try to solve all of them without using any global variables. And try on your own before looking at the solutions. Also please notify any error to me ( zobayer1[at]gmail[dot]com ).

Before looking at the problems, you may like to read this post about how to attack recursive problems.

__Problem 1:__

You will be given an array of integers, write a recursive solution to print it in reverse order.

Input:

5

69 87 45 21 47Output:

47 21 45 87 69

see answer

__Problem 2:__

Write a recursive function to print an array in the following order.

[0] [n-1]

[1] [n-2]

.........

.........

[(n-1)/2] [n/2]

Input:

5

1 5 7 8 9Output:

1 9

5 8

7 7

see answer

__Problem 3:__

Write a recursive program to remove all odd integers from an array.

**You must not use any extra array or print anything in the function.**Just read input, call the recursive function, then print the array in main().

Input:

6

1 54 88 6 55 7Output:

54 88 6

see answer

__Problem 4:__

Write a recursive solution to print the polynomial series for any input n:

1 + x + x

^{2}+ ................. + x

^{n-1}

Input:

5Output:

1 + x + x^2 + x^3 + x^4

see answer

__Problem 5:__

Write a recursive solution to evaluate the previous polynomial for any given x and n.

Like, when x=2 and n=5, we have 1 + x + x

^{2}+ ................. + x

^{n-1}= 31

Input:

2 5Output:

31

see answer

__Problem 6:__

Write a recursive program to compute n!

Input:

5Output:

120

see answer

__Problem 7:__

Write a recursive program to compute n

^{th}fibonacci number. 1

^{st}and 2

^{nd}fibonacci numbers are 1, 1.

Input:

6Output:

8

see answer

__Problem 8:__

Write a recursive program to determine whether a given integer is prime or not.

Input:

49

999983

1Output:

not prime

prime

not prime

see answer

__Problem 9:__

Write a recursive function that finds the gcd of two non-negative integers.

Input:

25 8895Output:

5

see answer

__Problem 10:__

Write a recursive solution to compute lcm of two integers. You must not use the formula lcm(a,b) = (a x b) / gcd(a,b); find lcm from scratch...

Input:

23 488Output:

11224

see answer

__Problem 11:__

Suppose you are given an array of integers in an arbitrary order. Write a recursive solution to find the maximum element from the array.

Input:

5

7 4 9 6 2Output:

9

see answer

__Problem 12:__

Write a recursive solution to find the

**second maximum**number from a given set of integers.

Input:

5

5 8 7 9 3Output:

8

see answer

__Problem 13:__

Implement linear search recursively, i.e. given an array of integers, find a specific value from it.

Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.

Input:

5

2 9 4 7 6

2

5 9Output:

not found

1

see answer

__Problem 14:__

Implement binary search recursively, i.e. given an array of

**sorted**integers, find a query integer from it.

Input format: first n, the number of elements. Then n integers. Then, q, number of query, then q integers. Output format: for each of the q integers, print its index (within 0 to n-1) in the array or print 'not found', whichever is appropriate.

Input:

5

1 2 3 4 5

2

3 -5Output:

2

not found

see answer

__Problem 15:__

Write a recursive solution to get the reverse of a given integer.

**Function must return an int**

Input:

123405Output:

504321

see answer

__Problem 16:__

Read a string from keyboard and print it in reversed order.

**You must not use any array to store the characters**. Write a recursive solutions to solve this problem.

Input:

hellooOutput:

oolleh

see answer

__Problem 17:__

Write a recursive program that determines whether a given sentence is palindromic or not just considering the alpha-numeric characters ('a'-'z'), ('A'-'Z'), ('0'-'9').

Input:

madam, i'm adam

hulalaOutput:

palindromic

not palindromic

see answer

__Problem 18:__

Implement strcat(), stracpy(), strcmp() and strlen() recursively.

Input:test on your ownOutput:test on your own

see answer

__Problem 19:__

If you already solved the problem for finding the n

^{th}fibonacci number, then you must have a clear vision on how the program flow works. So now, in this problem, print the values of your fibonacci function in pre-order, in-order and post-order traversal. For example, when n = 5, your program calls 3 and 4 from it, from the call of 3, your program calls 1 and 2 again....... here is the picture:

Input:

5Output:

Inorder: 1 3 2 5 2 4 1 3 2

Preorder: 5 3 1 2 4 2 3 1 2

Postorder: 1 2 3 2 1 2 3 4 5

see answer

__Problem 20:__

All of you have seen the tower of Hanoi. You have 3 pillars 'a', 'b' and 'c', and you need transfer all disks from one pillar to another. Conditions are, only one disk at a time is movable, and you can never place a larger disk over a smaller one. Write a recursive solution to print the moves that simulates the task, a -> b means move the topmost of tower a to tower b.

Input:

3Output:

a -> c

a -> b

c -> b

a -> c

b -> a

b -> c

a -> c

see answer

really nice :)

ReplyDeleteneed some critical recursion?

ReplyDeleteHaha, I have plenty :) I think these are enough for beginners to give them a head start, after these, they can practice on their own.

ReplyDeleteBut If you think that you can help them further, you can post here the problems, or source links or whatever you have.

Truly Helpful Brother...May Allah Bless you :)

ReplyDeleteইনফিনিটিভ(অসংখ্য) ধন্যবাদ।অনেক কিছু প্রেক্টিস করতে পারলাম।

ReplyDeleteসাকিব হাসান,ইবি,কুস্টিয়া,বাংলাদেশ।

I am really glad that it helped, my best wishes for you :)

DeleteI am trying to learn recursion.I can write easy recursion.But when I am trying to write a recursion for backtracking problem or dp, most of the time I failed.But if I see a medium hard recursive func I relaize it easily.But if I try to write a new recusion most of the time I failed.

ReplyDeleteActually, after solving lots of dp and recursive problem, this is what I would say: If you want to learn dp / backtracking algorithm, you have to solve as many dp as possible, the only way to improve dp skill is to solving more and more. Frustrating at some points, but I don't think there is any other options.

Deletewow!! It is very helpful for me and anyone . Thank you so much for this good job.

ReplyDeletethank u so much vai..............really helpful!

ReplyDeleteThat's damn important and fun ........................... Had a lot of fum :D

ReplyDeleteI'm glad that you liked it :)

DeleteI have tested the following code and it give me correct result But the answer script has one extra line before recursive call. the line is "if(*sbest < a[i]) *sbest = a[i];". Is it necessary? If necessary, would you kindly explain to me.

ReplyDeletevoid sMax(int i, int n, int *a, int *fbest, int *sbest)

{

if (i == n - 1)

{

*fbest = a[i];

return;

}

sMax((i + 1), n, a, fbest, sbest);

if (a[i] > *fbest)

{

*sbest = *fbest;

*fbest = a[i];

}

else if (a[i] > *sbest)

*sbest = a[i];

return;

}

কিছু কিছু Problem বুঝতে পারলাম না !

ReplyDeleteWhich ones?

Deleteint main(){

ReplyDeleteprintf("Thank you\n");

main();

}

haha, nice recursion, (but your program cannot call main() )

Deleteyou're welcome!

Can u plz tell me what's wrong with my code? All the time, it returns the correct ans with an extra value. why is there an extra?

ReplyDeleteint call(int i,int n,int a[])

{

if(i<=n)

{

cout<>n;

{

for(int i=0; i>a[i];

cout<<call(0,n-1,a)<<endl;

return 0;

}

}

Hi, your code is broken because of HTML characters. Can you post your code here and then give me the link?

Deletehttp://codepad.org/

Thanks so so so so so sooooooooooooooooooooooooooooooooooooooooooo much <3

ReplyDeleteYou are welcome :)

Deletehow i can write a recursive problem to generate all permutations of a given n numbers?

ReplyDelete//============================================================================

ReplyDelete// Name : TowerOfHanoiRecursion.cpp

// Author : Nitish Raj, Scientist, DRDO, raj.nitp@gmail.com

// Version :

// Copyright : No Copyright

// Description : Ansi-style

//============================================================================

#include

#include

#include

#include

using namespace std;

/*

| | |

___|___ __|__ __|__

Source Auxilary Destination

*/

/*Function say whenever you call this second argument will be always from where

you have to element and fourth argument says where you need to put and third used as

spare */

stack A,B,C;

void moveData(char Src, char Des){

switch(Src)

{

case 'a':

{

if(Des == 'b') B.push(A.top());

if(Des == 'c') C.push(A.top());

A.pop();

break;

}

case 'b':

{

if(Des == 'a') A.push(B.top());

if(Des == 'c') C.push(B.top());

B.pop();

break;

}

case 'c':

{

if(Des == 'b') B.push(C.top());

if(Des == 'a') A.push(C.top());

C.pop();

break;

}

}

}

void ShowDataofStack(){

stack temp;

cout<<"TOWER A :: ";

temp = A;

while(!temp.empty()){

cout<0)

{

HanoiTowerRec(n-1, Source,Destination, Aux); //

// Now nth element left on Source so put this to Destination;

cout<<"______________________________________ "<"<>n;

for(int i =0 ; i<n;i++) A.push(n-i);

HanoiTowerRec(n, 'a', 'b', 'c');

return 0;

}

/**

ReplyDeleteWrite a recursive solution to evaluate the previous polynomial for any given x and n.

Like, when x=2 and n=5, we have 1 + x + x2 + ................. + xn-1 = 31

Input:

2 5

Output:

31

**/

#include

using namespace std;

int print(int i,int x,int n,int sum)

{

if(i==1)

{

sum=1;

}

if(i>1)

{

sum+=pow(x,i-1);

}

if(i==n)

return sum;

print(i+1,x,n,sum);

}

int main()

{

cout<<print(1,2,5,0)<<endl;;

return 0;

}

ভাইয়া আমি এইভাবে করছি। আমারটা কি হইছে? নাকি কোন বাগ আছে? জানালে ভালো হত।

Why do you set sum = 1 when i == 1.

Deletesakhawatshamim35@gmail.com এই ইমেইল ও জানাতে পারেন।

ReplyDeletereally its too helpful.

ReplyDeleteproblem 12,20 seems very difficult than others .

ReplyDeleteCan anyone tell what is use of return statement while returning a value in recursion...

ReplyDeleteWhat if I don't write return in front of function naming which is not of void type?

It will raise warning during compilation, also, the method will return a garbage value if any statement that called the function initially was expecting a value. If you do not expect a return value from a function call, then there is not problem. Look at the following example:

Deleteint a() {

// do not return anything

}

---- in main ---

a(); // no problem

int x = a(); // now there is a problem

I hope this clears up the confusion.