Computing Concepts with C++ Essentials, 3rd ed.
Laboratory Notebook
Chapter 14 - Recursion

John P. Russo


Your name:
Your email address:
Your student ID number:

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.


Lab Objectives

To gain experience with


P1. A Simple Recursion Example

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;
}


R1. Computing the Greatest Common Divisor (GCD): The Euclidean Algorithm

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:

30/3 = 10 45/3 = 15
30/5 = 6 45/5 = 9
30/15 = 2 45/15 = 3
Since we cannot divide any further, the greatest common divisor is 15.
To make sure that you understand the greatest common divisor, please complete the following table:

X

Y

GCD(X,Y)

25 55
300 175
160 80
459 76
456 76

The Euclidean Algorithm states the following, given that a and b are positive integers that we wish to find the gcd of:

a=q1b + r1 , 0<r1<b
b=q2r1 + r2, 0<r2<r1
r3=q3r2 + r3 , 0<r3<r2
. . . . . . . . . . . . . . . . . . .  
ri=qi+2ri+1 + ri+2 , 0<ri+2<ri+1
. . . . . . . . . . . . . . . . . . .  
rk-2 =qkrk-1 + rk , 0<rk<rk-1
rk-1 = qk+1rk ,  

So, rk , the last non-zero remainder is the GCD.

Let's look at an example: find GCD(412,36)

412 = 11(36) + 16 0 < 16 < 36
36 = 2(16) + 4 0 < 4 < 16
16 = 4(4) + 0  
Since 4 is the last non-zero remainder, GCD(412,36) = 4.

For practice, compute GCD(250,111) using the steps shown above.


P2. Non-Recursive Euclidean GCD

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.


R2. Thinking Recursively

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):

412 = 11(36) + 16 0 < 16 < 36 (1)
36 = 2(16) + 4 0 < 4 < 16 (2)
16 = 4(4) + 0   (3)

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

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.


P3. Recursive Implementation of Euclidean GCD Algorithm

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.


R3. Efficiency of Recursion

Which implementation of the Euclidean Algorithm do you think is more efficient?

Why?


P4. Efficiency

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.