Please answer the following problems. NO POINTS WILL BE AWARDED IF ALL PROBLEMS
ID: 3551971 • Letter: P
Question
Please answer the following problems. NO POINTS WILL BE AWARDED IF ALL PROBLEMS ARE NOT SOLVED!!
1. write a recursive function that returns the number of digits in a nonnegative integer
2. For the following recursive function:
int F (int n)
{
if (n == 0)
return 0;
else
return n + F (n - 1);
}
a. find F (0)
b. suppose + is changed to * in the inductive step, find F (5)
3. assume ASCII representation of characters and the following function F ( ):
void F (char ch)
{
if ('A' <= ch) and (ch <= 'H'))
{
F (ch - 1);
cout << ch;
}
else
cout << endl;
}
Tell what output will be produced by the function call:
a. F('C')
b. F('G')
c. F('C') if ch - 1 is replaced by ch + 1 in the function
4. Given the following function F ( ) and assuming ASCII representation of characters. Use the method illustrated below to trace
the sequence of function calls and returns in evaluating F('a', 'e') and F(''h', 'c')
int F (char ch1, char ch2)
{
if (ch1 > ch2)
return 0;
if (ch1 + 1 == ch2)
return 1;
else
return F (ch1 + 1, ch2 - 1) - 2;
}
5. Determine what is calculated by the recursive functions below: ( NO CODE...ex. prints out sum, prints middle digit,...ect)
a. unsigned F (unsigned n)
{
if (n == 0)
return 0;
else
return n * F(n - 1);
}
b. unsigned F (double x, unsigned n)
{
if (n == 0)
return 0;
else
return n + F(x, n - 1);
}
c. unsigned F (unsigned n)
{
if (n < 2)
return 0;
else
return 1 + F(n / 2);
}
d. unsigned F (unsigned n)
{
if (n == 0)
return 0;
else
return F(n / 10) + n % 10;
}
e. unsigned F (int n)
{
if (n < 0)
return F(-n);
if (n < 10)
return n;
else
return F(n / 10);
}
6. Write recursive definitions of the functions whose prototypes are given below:
a. void ReverseArray (ArrayType a, int first, int last);
/ * Reverse the contents of a (first), .... a (last) * /
b. int SumArray (ArrayType a, int n);
/ * Return the sum of a (1), .... a (n) * /
c. int Location (ArrayType a, int first, int last, Element elm);
/ * Return the location of elm in a (first), ...., a (last). If not found, return 0. * /
d. The greatest common divisor of two integers a and b GCD(a,b) not both of which are zero is the largest positive integer that
divides both a and b. The Euclidean algorithm for finding this GCD of a and b is as follows: Divide a by b to obtain the integer quotient q and the remainder r so that a =bq + r (if b = 0, GCD (a,b) = a). Then GCD(a,b) = GCD(b,r). Replace a with b and b with r
and repeat this procedure. Because the remainders are decreasing eventually a remainder of 0 will result. The last nonzero remainder is GCD(a,b,). For example:
1260 = 198 * 6 / 72 GCD(1260,198) = GCD(198, 72)
198 = 72 * 2 / 54 = GCD(72 ,54)
72 = 54 * 1 / 18 = GCD(54, 18)
54 = 18 * 3 / 0 = GCD(18)
(Note: If either a or b is negative replace them with their absolute values in this algorithm.) Write a recursive greatest common divisor function.
Explanation / Answer
1. //Recursive function to calculate number of digits of a non-negative integer
int n_digits(int n){
if(n==0) return 0;
else return 1 + n_digits(n/10);
}
2.
(a) F(0) = 0
(b) F(5) = 0
3.
(a) F('C') = ABC
(b) F('G") = ABCDEFG
(c) F('C') = HGFEDC
4.
(a) For F('a', 'e'):
Call: (a, e)
Call: (b, d)
Call: (c, c)
Call: (d, b)
return: 0
return: -2
return -4
return -6
(b) For F('h', 'c'):
Call: (h, c)
return: 0
5.
a. Always prints 0
b. prints the value (n + n-1 + n-2 + ...+ 0 = ) n(n+1)/2
c. prints the greatest integer less than or equal to log(n) [base = 2] (For 0, the value is 0]
d. Prints the sum of digits of n
e. Prints the first (most significant digit) in n [Ex: F(432) = 4]
6.
(a)
void ReverseArray (ArrayType a, int first, int last){
if(first <= last){
Element tmp = a(last); //Assuming the array elements have type 'Element'
a(last) = a(first);
a(first) = tmp;
ReverseArray(a, first+1, last-1);
}
}
(b)
int SumArray (ArrayType a, int n){
int sum = 0;
for(int i=1; i<=n; i++){
sum = sum + a(i);
}
return sum;
}
(c)
int Location (ArrayType a, int first, int last, Element elm){
int loc = 0;
for(int i = first ; i <= last; i++){
if(a(i)==elm) {
loc = i;
break;
}
}
return loc;
}
(d)
int GCD(int a, int b){
if(a<0) a *= -1;
if(b<0) b *= -1;
if(a==0) return b;
else if(b==0) return a;
else{
int rem = a%b;
return GCD(b, rem);
}
}