Recursion Problem Solve

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 47

Output:
47 21 45 87 69

#include<bits/stdc++.h>
using namespace std;

void fun(int a[], int i, int n)
{
    if(i<n)
    {
        fun(a, i+1, n);
        cout << a[i] << " ";
    }
}

int main()
{
    int n;
    cin >> n;

    int a[n];
    for(int i=0; i<n; i++)
        cin >> a[i];

    fun(a, 0, n);

    return 0;
}

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 9

Output:
1 9
5 8
7 7

#include<bits/stdc++.h>

using namespace std;

void fun(int a[], int i, int j)

{

    if(i > j)

        return;

    cout << a[i] << " " << a[j] << "\n";

    fun(a, i+1, j-1);

}

int main()

{

    int n;

    cin >> n;

    int a[n];

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

        cin >> a[i];

    fun(a, 0, n-1);

    return 0;

}

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 7

Output:
54 88 6

#include<bits/stdc++.h>

using namespace std;

int a[1000];

void fun(int i, int n)

{

    if(i >= n)

        return;

    if(a[i]%2 == 1)

        a[i] = -10e6;

    fun(i+1, n);

}

int main()

{

    int n;

    cin >> n;

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

        cin >> a[i];

    fun(0, n);

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

    {

        if(a[i] == -10e6)

            continue;

        cout << a[i] << " ";

    }

    return 0;

}

Problem 4:

Write a recursive solution to print the polynomial series for any input n:
1 + x + x² + ................. + x^n-1

Input:
5

Output:
1 + x + x^2 + x^3 + x^4

#include<bits/stdc++.h>
using namespace std;

void fun(int i, int n)
{
    if(i == n-1)
    {
        cout << "X^" << i << "\n";
        return;
    }

    if(i == 0)
        cout << "1 + ";

    else if(i == 1)
        cout << "X + ";

    else
        cout << "X^" << i << " + ";

    fun(i+1, n);
}

int main()
{
    int n;
    cin >> n;

    fun(0, n);

    return 0;
}

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² + ................. + x^n-1 = 31

Input:
2 5

Output:
31

#include<bits/stdc++.h>
using namespace std;

int fun(int i, int n, int x, int sum = 0)
{
    if(i > n-1)
        return sum;

    sum += pow(x, i);

    return fun(i+1, n, x, sum);
}

int main()
{
    int x, n;
    cin >> x >> n;

    cout << fun(0, n, x) << "\n";

    return 0;
}

Problem 6:

Write a recursive program to compute n!

Input:
5

Output:
120

#include<bits/stdc++.h>
using namespace std;

int fact(int n)
{
    if(n == 0)
        return 1;

    return n*fact(n-1);
}

int main()
{
    int n;
    cin >> n;

    cout << fact(n) << "\n";

    return 0;
}

Problem 7:

Write a recursive program to compute n^th fibonacci number. 1^st and 2^nd fibonacci numbers are 1, 1.

Input:
6

Output:
8

#include<bits/stdc++.h>

using namespace std;

int fibo(int n)

{

    if(n == 0)

        return 0;

    if(n == 1)

        return 1;

    return fibo(n-1) + fibo(n-2);

}

int main()

{

    int n;

    cin >> n;

    cout << fibo(n) << "\n";

    return 0;

}

Problem 8:

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

Input:
49
999983
1

Output:
not prime
prime
not prime

#include<bits/stdc++.h>

using namespace std;

int prime(int n, int i=2)

{

    if(n < 2)

        return 0;

    if(n == 2 || n == 3 || i*i > n)

        return 1;

    if(n%i == 0)

        return 0;

    return prime(n, i+1);

}

int main()

{

    int n;

    cin >> n;

    int f = prime(n);

    if(f == 0)

        cout << "not prime" << "\n";

    else

        cout << "prime" << "\n";

    return 0;

}

Problem 9:

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

Input:
25 8895

Output:
5

#include<bits/stdc++.h>

using namespace std;

int gcd(int a, int b)

{

    if(b == 0)

        return a;

    return gcd(b, a%b);

}

int main()

{

    int a, b;

    cin >> a >> b;

    cout << gcd(a, b) << "\n";

    return 0;

}

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 488

Output:
11224

#include<bits/stdc++.h>

using namespace std;

int lcm(int n, int a, int b)

{

    if(n%a == 0 && n%b == 0)

        return n;

    return lcm(n+1, a, b);

}

int main()

{

    int a, b;

    cin >> a >> b;

    cout << lcm(min(a, b), a, b) << "\n";

    return 0;

}

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 2

Output:
9

#include<bits/stdc++.h>

using namespace std;

int maximum(int a[], int n)

{

    if(n == 0)

        return a[0];

    return max(a[n], maximum(a, n-1));

}

int main()

{

    int n;

    cin >> n;

    int a[n];

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

        cin >> a[i];

    cout << maximum(a, n-1) << "\n";

    return 0;

}

Problem 12:

Write a recursive solution to find the second maximum number from a given set of integers.

Input:
5
5 8 7 9 3

Output:
8

#include<bits/stdc++.h>

using namespace std;

int maximum(int a[], int i, int n, int mx1=-10e5, int mx2=-10e5)

{

    if(i >= n)

    {

        if(mx2 == -10e5)

            mx2 = mx1;

        return mx2;

    }

    if(a[i] < mx1 && a[i] > mx2)

        mx2 = a[i];

    if(a[i] > mx1)

    {

        mx2 = mx1;

        mx1 = a[i];

    }

    return maximum(a, i+1, n, mx1, mx2);

}

int main()

{

    int n;

    cin >> n;

    int a[n];

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

        cin >> a[i];

    cout << maximum(a, 0, n-1) << "\n";

    return 0;

}

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 9

Output:
not found
1

#include<bits/stdc++.h>

using namespace std;

void searchs(int a[], int i, int n, int s)

{

    if(i > n)

    {

        cout << "not found" << "\n";

        return;

    }

    if(a[i] == s)

    {

        cout << i << "\n";

        return;

    }

    searchs(a, i+1, n, s);

}

int main()

{

    int n, q, s;

    cin >> n;

    int a[n];

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

        cin >> a[i];

    cin >> q;

    while(q--)

    {

        cin >> s;

        searchs(a, 0, n-1, s);

    }

    return 0;

}

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 -5

Output:
2
not found

#include<bits/stdc++.h>

using namespace std;

void binary(int a[], int low, int height, int s)

{

    if(low > height)

    {

        cout << "not found" << "\n";

        return;

    }

    int m = (low + height)/2;

    if(s == a[m])

    {

        cout << m << "\n";

        return;

    }

    if(s < a[m])

        return binary(a, low, m-1, s);

    return binary(a, m+1, height, s);

}

int main()

{

    int n, q, s;

    cin >> n;

    int a[n];

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

        cin >> a[i];

    cin >> q;

    while(q--)

    {

        cin >> s;

        binary(a, 0, n-1, s);

    }

    return 0;

}

Problem 15:

Write a recursive solution to get the reverse of a given integer. Function must return an int

Input:
123405

Output:
504321

#include<bits/stdc++.h>

using namespace std;

int fun(int n, int r=0)

{

    if(n == 0)

        return r;

    int a = n%10;

    n = n/10;

    r = r*10 + a;

    return fun(n, r);

}

int main()

{

    int n;

    cin >> n;

    cout << fun(n) << "\n";

    return 0;

}

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:
helloo

Output:
oolleh

#include<bits/stdc++.h>

using namespace std;

void fun(int i, string s)

{

    if(i >= s.size())

        return;

    fun(i+1, s);

    cout << s[i];

}

int main()

{

    string s;

    cin >> s;

    fun(0, s);

    return 0;

}

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
hulala

Output:
palindromic
not palindromic

#include<bits/stdc++.h>

using namespace std;

bool check(string s, int n)

{

    if((s[n]>=48 && s[n]<=59) || (s[n]>=65 && s[n]<=90) || (s[n]>=97 && s[n]<=122))

        return true;

    return false;

}

void fun(int s, int e, string str)

{

    if(s > e)

    {

        cout << "Palindromic" << "\n";

        return;

    }

    if(check(str, s) && check(str, e))

    {

        if(str[s] != str[e])

        {

            cout << "not Palindromic" << "\n";

            return;

        }

        s++;

        e--;

        return fun(s, e, str);

    }

    if(check(str, s) == false)

        s++;

    else

        e--;

    return fun(s, e, str);

}

int main()

{

    string str;

    getline(cin, str);

    int s = 0, e = str.size()-1;

    fun(s, e, str);

    return 0;

}