Once this form has been customized for your institution, you can use this button to send your lab work. Be sure to read the instructions before starting your work.
To gain experience with
Consider a function int digits(int) which finds the number of digits needed to represent an integer. For example, digits(125) is 3 because 125 has three digits (1, 2, and 5). The algorithm is defined as:
if n < 10, then digits(n) equals 1. Else, digits(n) equals digits(n / 10) + 1.
(Why? If n is less than 10, one digit is required. Otherwise, n requires one more digit than n/10.)
For example, if called as int num_digits = digits(1457), the following trace results:
digits(1457) = digits(145) + 1 = digits(14) + 1 + 1 = digits(1) + 1 + 1 + 1 = 1 + 1 + 1 + 1
Do a trace of digits(32767)
Write int digits(int) to be called by the following main():
int main() { int test_value; cout << "Please enter a number " << "\n"; cin >> test_value; int ndigits = digits(test_value); cout << "You need " << ndigits << " digits to represent " << test_value << " in decimal\n"; return 0; }
/* paste program here */
In order to illustrate recursion in this lab, we will use an example from mathematics: the greatest common divisor, or GCD. The greates common divisor is defined as the largest divisor of a pair of integers. For example, if we try to find all of the common divisors of 30 and 45, we get the following:
X
Y
GCD(X,Y)
The Euclidean Algorithm states the following, given that a and b are positive integers that we wish to find the gcd of:
So, r_{k} , the last non-zero remainder is the GCD.
Let's look at an example: find GCD(412,36)
For practice, compute GCD(250,111) using the steps shown above.
*paste your answer here
Now that you know how the Euclidean Algorithm for computing the gcd works, implement this by creating a class which has two integers as data elements a constructor and a member function to compute the gcd. Please make sure that you test to make sure that the integers are positive. You can use the modulus (%) operator to calculate the remainder. Your program should prompt the user for two integers and then return the GCD.
/*paste your code here
Now that you have coded the Euclidean GCD Algorithm non-recursively, let's once again look at the algorithm. Your textbook discusses some steps for reducing a problem to a simpler solution in order to implement it recursively.. Let's take our example from above gcd(412,36):
Since 4 is the last non-zero remainder, the Euclidean algorithm tells us that this is the gcd. But let's look again at equation 2: if we just use equations 2 and 3, we will find that the gcd(36,16) = 4. Similarly, equation 3 used alone tells us that gcd(16,4) = 4 because 4 divides 16. So, we can the say that:
gcd(412,36)=gcd(36,16)=gcd(16,4)
We can see that:
16 = 412 mod 36 and 4 = 36 mod 16
Therefore:
gcd(412,36) = gcd(36,412 mod 36) = gcd(412 mod 36,36 mod (412 mod 36))
We can therefore write out the steps for representing this as a recursive function:
given that x and y are positive integers
1. if x mod y = 0, then gcd(x,y) = y
2. if x does not divide by y evenly, then
a. set x = y b.set y = x mod y, where the value of x is the old value of x c. return to step 1
a. set x = y
b.set y = x mod y, where the value of x is the old value of x
c. return to step 1
Let's walk through the example gcd(412,36)
1. 412 mod 36 != 0, goto step 2
2a. x = 36
2b. y = 412 mod 36 = 16
2nd iteration:
1. 36 mod 16 != 0
2a. x = 16
2b. y = 4
3rd iteration
1. 16 mod 4 = 0 , return 4
As you can see, we have broken the problem down into simpler problems in order to solve it.
Now that we have gone through the recursive implementation of this algorithm, modify the class that you created in P2 to implement the gcd member function as a recursive function.
Which implementation of the Euclidean Algorithm do you think is more efficient?
Why?
Write a program to trace your recursive implementation of GCD.
Run this program. Do you see any place where there could be some inefficiencies in your code? Do you think that the non-recursive (iterative) version is faster?
Don't forget to send your answers when you're finished.