*******PLEASE COMPLETE IN C******** Program 1 - Some General Recursive Algorithm
ID: 3698740 • Letter: #
Question
*******PLEASE COMPLETE IN C********
Program 1 - Some General Recursive Algorithms As we discussed in class, recursion is a very useful programming technique in which a function makes a call to itself. Such a call is described as a "recursive function call." Recursion can be applied successfully to any problem in which the overall solution can be calculated from smaller portions of the original problem. Although it incurs extra overhead in terms of time and memory, recursion's main advantage is that it can often vastly simplify the code. The following examples will illustrate this. For this assignment, let's write recursive functions that solve three different problems: 1) Determining if a string is a palindrome or not. 2) Printing the characters of a string backwards instead of forwards. 3 Calculating the Greatest Common Divisor (GCD) of two integers. 4)Recursive Linear Search All of these problems should be solved by a separate recursive function. You can determine what the prototypes should be. In all cases, analyze the problem space for two characteristics: (a) what the base case should be, and (b) how a larger problem can be solved by making recursive calls to smaller, but similar problems. That will tell you how to set up the selection logic statement that is necessary in a recursive function In general, your program should do the following: For Problems (1) and (2) above, ask the user to input a character string. For Problem (1), determine whether the string is a palindrome or not by using a recursive function and report the result to the user. For Problem (2), print the string in reverse (also by usinga recursive function) 1)Explanation / Answer
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
bool isPalindrome(char arr[], int p, int r)
{
// if the current string has only one character
// it is palindrome
if( p == r )
return true;
// if the characters at the terminals don't match
if( arr[p] != arr[r] )
return false;
if( p < r + 1 )
// recursively check if the passed string is palindrome
return isPalindrome( arr, p + 1 , r - 1 );
return true;
}
int gcd(int x, int y)
{
if( x % y == 0 )
return y;
else
return gcd( y , x % y );
}
// i is the current index of the character which should be printed
// n is length of str
void printBackwards(char str[], int i, int n)
{
if( i >= n )
return;
// recursively print the right substring backward
printBackwards( str, i + 1 , n );
printf("%c", str[i]);
}
// i is the current index of the integer which is to be searched
// n is length of arr
// key is to be found
// return -1 if key is not found
int linear_search(int arr[], int n, int i, int key)
{
// if key is not found
if( i >= n )
return -1;
// if key is found
if( arr[i] == key )
return i;
// search in the right subarray
int x = linear_search( arr, n , i + 1 , key );
return -1;
}
// p is the starting index
// r is the ending index
// key is to be found
// return -1 if key is not found
int binarySearch(int arr[], int p, int r, int key)
{
if( p <= r )
{
int mid = ( p + r ) / 2;
// if element is found
if( arr[mid] == key )
return mid;
// if key lies in right subarray
else if( arr[mid] < key )
return binarySearch( arr, mid + 1 , r , key );
// if key lies in left subarray
else
return binarySearch( arr, p , mid - 1 , key );
}
else
return -1;
}
int main()
{
char str[40];
printf("Enter a string : ");
scanf("%s", str);
if( isPalindrome(str, 0 , strlen(str) - 1) )
printf("%s is palindrome.");
else
printf("%s is not a palindrome.");
printf(" Enter two integers : ");
int x, y;
scanf("%d%d", &x, &y);
printf("The GCD of %d and %d is %d .", x, y, gcd(x,y));
int arr[] = { 1 , 3, 5, 6, 8, 10, 15 };
if( linear_search(arr, 7, 0 , 5) )
printf(" 5 is present in array.");
else
printf(" 5 is not present in array.");
if( binarySearch(arr, 0 , 6 , 5) )
printf(" 5 is present in array.");
else
printf(" 5 is not present in array.");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.