USING C CODE PLEASE add comments for every line please As we discussed in class,
ID: 3700262 • Letter: U
Question
USING C CODE PLEASE
add comments for every line please
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:
1) 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 using a recursive function).
2) For Problem (3), ask the user to enter two integers. Determine the GCD by using a
recursive function and report the result to the user. An example run of the program might look like this:Please enter a character string: abdef
3) For Problem (4), use the 150 element data array we used in HW 5. You may initialize the array with an initialization list as we did in HW 5. As described below, at the minimum test the function on the numbers 71, 2400, 1988, and 2567. The first three are in the array and the last one is not. (Note that both the first and last element of the array are included in the test set. This is very good from a program testing viewpoint.)
Some programming notes that will help:
1) Palindromes
A palindrome is a string that reads the same forwards or backwards. For example, theword “radar” is a palindrome, while the word “apple” is not (“apple” ? “elppa”). Note that palindromes do not have to be meaningful words. For example, the string“abcddcba” is also a palindrome. Finally, palindromes can be of even or odd length. Your function should be able to handle both.
Any palindrome must begin and end with the same character. In addition, the interior portion of a palindrome, that is, the part of the string that omits the first and last character, must also be a palindrome. This is the portion of the string on which your function can make a recursive call.
Write your function to return 1 if the string is a palindrome, and 0 if it is not. In this problem, let us treat lower and upper case letters as distinct characters. (Therefore, the string “ABa” would not be a palindrome.)
2) Printing a character string backwards
For this problem, your function does not need to return a value. Just have it recursively
print the characters of a string backwards.
(What change would cause the recursive function print the characters forwards?)
3) Greatest Common Divisor
The Greatest Common Divisor of two integers is the largest integer that evenly divides them both. For example, the GCD of 16 and 24 is 8, the GCD of 18 and 24 is 6, and the GCD of 17 and 24 is 1. Note that the GCD does not have to be a prime.
The recursive formulation for this problem is given in Problem 5.39 on page 211 of our book. In general, the GCD of integers x and y is defined recursively as follows: If y is equal to 0, then GCD(x,y) is x; otherwise, GCD (x,y) is GCD (y, x%y).
Have your function return the GCD of x and y as an int.
4) Recursive Linear Search
Implement a recursive linear search algorithm as we discussed in class. You may use the data array that we used in the previous homework (i.e., 150 random numbers between 0 and 3000). Include a (global) counter that counts the number of recursive calls made. Ask the user for the key to search for in each case, and report back whether the number was found or not and the number of function calls that were made. Verify your algorithm on the following five numbers at least: 71 (position 0, 1 function call), 2400 (position 149, 150 function calls), 1988 (position 125, 126 function calls), 2567 (not found, 151 function calls).
Here are some sample runs:
Please enter the search key: 2574
FOUND: Key 2574 was located at position 134. # of function calls: 135 Please enter the search key: 2567
NOT FOUND: Key 2567 was not located in the data set.
Do you see a relationship between the number of function calls and the index position of the element (if it is found)?
5) 5 Point Bonus (Challenging)
Re-implement the Recursive Linear Search algorithm, but this time use a divide and
conquer approach similar to the Binary Search. In general terms, do the following:
a) Determine the mid-point of the current array.
b) Recursively call the function on both the left and right halves of the array.
c) Compare the results from the two halves and report back the larger of the two as
the answer. (Note that -1 indicates the number was not found, whereas, if it was found, the return value will be an index >= 0.)
In this function, also include a counter that counts the number of function calls. How does this number compare to the number produced by the previous recursive linear search algorithm? Why is this number so much larger?
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) 2) Determining if a string is a palindrome or not. Printing the characters of a string backwards instead of forwards. Calculating the Greatest Common Divisor (GCD) of two integers. 4)Recursive Lincar Scarch 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 recursiv ve function. In general, your program should do the following: 1 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 using a recursive function).Explanation / Answer
C CODE WITH EXPLANATION:
#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.