Question

Please solve this question in C++ language using recursion.

Q (1) Write functions for each of the following problems. Each problem should be solved by writing a recursive function. Your final program should not have any loops in it.

1. Write a function that uses recursion to raise a number to a power. The function should take two arguments, the number to be raised to the power (floating point) and the power (a non-negative int).                                                                                       (10 Points)

2. Write a boolean function named isMember that takes two arguments: an array of type char and a value. It should return true if the value is found in the array, or false if the value is not found in the array.                                                             (10 Points)
3. A palindrome is any word, phrase, or sentence that reads the same forwards or backwards. Here are some palindromes:                                                      

Level

Civic

Pot top

A man a plan a canal Panama

Write a boolean function that determines if a string argument is a palindrome. The function should return true if the argument reads the same forwards and backwards. Your function should ignore spaces and be case-insensitive. Assume the input is just letters and spaces.                                                                                         (20 Points)

Answer 1

Part a.

/* This function calculated recursively the power of b raised by exponent e i.e. b^e.
 * Full explanation is provided inside the function. Here I give an example how its working
 * Suppose we want to calculate 3^6 then first we calculate 3^3 and then we calculate 3^1 then we calculate 3^0
 */
float power(float b, int e) {
        // if expoenent is 0 then power of any number is 1 so we return 1
        if(e == 0)
                return 1;
        // now we calculate recursively half of the power
        float x = power(b, e/2);
        // if e is even then power is multiplication of x and x because we can write 3^4 = 3^2 * 3^2.
        // but if e is odd then it is b*x*x because for 2^5 we can write 3^5 = 3^2 * 3^2 * 3
        if(e % 2 == 0)
                return x * x;
        else
                return b * x * x;
}

Part b.

/* This function takes pointer to character array as input and the character which needs to be found
 * First we check if the array is empty using strlen() function. If it is empty then we return false as characer could not be found
 * If arr[0] is equal to c then we return true
 * Else we recurse and starts finding by passing position to one plus the previous array position.
 * Example if arr = {a, e, i} and we need to find 'e' then first it checks arr[0] == 'e' or not. as it is not true we recurse for arr+1 i.e. arr is now [e, i]
 * as arr[0] = 'e' and we need to find 'e' and we have found so we return true
 */
bool isMember(char *arr, char c) {
        // if length is 0 then we return false
        if(strlen(arr) == 0)
                return false;
        // if 0th position has the character then we return true
        if(arr[0] == c)
                return true;
        // else we recurse for arr+1 i.e. next position in the array
        return isMember((arr+1), c);
}

Part c.

/* This function takes 1 argument string s - string which needs to be checked if it is palindrome or not
 * We first check the length of the string s. If it is 0 or 1 then it is palindrome. This is our base condition
 * Then we check if 0th or last position has white space or not if it has white space then we recurse for substring
 * we check s[0] and s[len-1] if any of them is an upper case alphabet we add 32 to it to make it lower case because ASCII value of 'A' is 65 and that of 'a' is 97.
 * if s[0] == s[len-1] after conversion of uppercase to lowercase then we recurse for substring(0, len-1)
 * if they are not equal then we return false
 */
bool isPalindrome(string s) {
        int len = s.length();
        // if len is 1 or 0 then return true
        if(len <= 1)
                return true;
        // if 0th position has white space then recurse for substring from 1st position
        if(s[0] == ' ')
                return isPalindrome(s.substr(1, s.length()));
        // if last position has white space then recurse from 0 to len-1
        if(s[len-1] == ' ')
                return isPalindrome(s.substr(0, len-1));
        // if 0th or (len-1)th position has uppercase alphabet convert it into lower case by adding 32 to it
        if(s[0] >= 'A' && s[0] <= 'Z')
                s[0] += 32;
        if(s[len-1] >= 'A' && s[len-1] <= 'Z')
                s[len-1] += 32;
        // if first and last element are not equal we return false
        if(s[0] != s[len-1])
                return false;
        // else we recurse for substring between first and last element
        return isPalindrome(s.substr(1, len-2));
}