Question

using recursion
no loops allowed(for,while..ect) not allowed

#4: Write a recursive function ‘bool palindrome(string s)’ that returns true if s is a palindrome and false if not.


#5: Write a recursive function 'void reverse(string &word)' that reverses the given input string.

string name = "damian";
reverse(name);
cout << name << endl;  //should display "naimad".

#6: Write a function 'string binary(int n)' that returns a string of 1's and 0's which is the binary representation of n.

cout << binary(43) << endl; // 101011

#7: Write a function 'int numTwos(int n)' which returns the number of 2's in the base-4 expansion of n.

cout << numTwos(2170) << endl; // 3

c++

Answer 1

Write a recursive function ‘bool palindrome(string s)’ that returns true if s is a palindrome and false if not.

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

// recursive function which
// check if s is
// palindrome or not.
bool check(char s[],
                        int start, int end)
{

        // If there is only one character
        if (start == end)
        return true;

        // If first and last
        // characters do not match
        if (s[start] != s[end])
             return false;

        // If there are more than
        // two characters, check if
        // middle substring is also
        // palindrome or not.
        if (start < end + 1)
             return check(s, start + 1, end - 1);

   return true;
}

bool palindrome(char s[])
{
        int length = strlen(s);

        if (length == 0)
                  return true;

        return check(s, 0, length - 1);
}

// Driver Code
int main()
{
        char s[] = "hellolleh";

        if (palindrome(s))
        cout << "true";
        else
        cout << "false";

        return 0;
}

Write a recursive function 'void reverse(string &word)' that reverses the given input string.

#include <iostream>
#include <algorithm>
using namespace std;

// recursive function to reverse a given string note string is passed as reference parameter
void reverse(string &str, int p)
{
        static int i = 0;

        // if we have reached the end of the string
        if (p == str.length())
                return;

        reverse(str, p + 1);

        if (i <= p)
                swap(str[i++], str[p]);
}

// Reverse given string using Recursion
int main()
{
        string str = "damian";

        reverse(str, 0);
        cout<< str;

        return 0;
}

Write a function 'string binary(int n)' that returns a string of 1's and 0's which is the binary representation of n.

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

// decimal to binary conversion using recursion
int binary(int number)
{
        if (number == 0)
                return 0;
        else
                return (number % 2 + 10 *
                                binary(number / 2));
}

int main()
{
        cout << binary(43);
        return 0;
}

Write a function 'int numTwos(int n)' which returns the number of 2's in the base-4 expansion of n.

// C Program to convert decimal to any given base
#include<iostream>
#include <stdio.h>
#include <string.h>
using namespace std;

int c=1;
// return char for a value. For example '2' is returned for 2. 'A' is returned for 10. 'B' for 11
char val(int n)
{
        if (n >= 0 && n <= 9)
                return (char)(n + '0');
        else
                return (char)(n - 10 + 'A');
}

// Utility function to reverse a string
void strev(char *str)
{
        int len = strlen(str);
        int i;
        for (i = 0; i < len/2; i++)
        {
                char temp = str[i];
                str[i] = str[len-i-1];
                str[len-i-1] = temp;
        }
}

// Function to convert a given decimal number
// to a base 'base' and
char* fromDeci(char res[], int base, int inputNum)
{
        int index = 0; // Initialize index of result

        // Convert input number is given base by repeatedly
        // dividing it by base and taking remainder
        while (inputNum > 0)
        {
                res[index++] = val(inputNum % base);
                inputNum /= base;
        }
        res[index] = '\0';

        // Reverse the result
        strev(res);

        return res;
}

int numTwos(int num)
{
    if(num==0)
        return c;
    else
    {
        if(num%10==2)
            c++;
        num=num/10;
        numTwos(num);
    }

}

// Driver program
int main()
{
        int num1 = 2170, base = 4;
        char res[100];
    char* num=fromDeci(res, base, num1);
    cout<<num;
    int x=(int)(num);
    cout<<endl;
    cout<<"number of 2's: "<< numTwos(x);
        return 0;
}