In a previous lab you implemented an iterative version of the Euclidean algorith

Question

In a previous lab you implemented an iterative version of the Euclidean algorithm for finding the Greatest Common Divisor between two integer values. This problem has an elegant and simple recursive solution.

Recall that 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 greatest common divisor of a and b is as follows:

- Divide a by b to obtain the integer quotient q and remainder r so that a = bq + r. Note: if b = 0, then GCD(a,b) = a.

- Now, GCD(a,b) = GCD(b,r) so replace a with b and b with r, and repeat this procedure

Since the remainders are decreasing, eventually a remainder of 0 will result. The last nonzero remainder is GCD(a,b). For example,

1260 = 198 x 6 + 72 GCD(1260,198) = GCD(198,72)

199 = 72 x 2 + 54 GCD(1260,198) = GCD(72,52)

72 = 54 x 1 + 18 GCD(1260,198) = GCD(54,18)

54 = 18 x 3 + 0 GCD(1260,198) = 18

Write a recursive implementation of the Euclidean GCD function function:

int gcd(int a, int b);

[Hint: Note that when the remainder is zero, the divisor will be the GCD]

Write a short program to test your GCD function with the following values:

1280,198

197,13

120,60

Explanation / Answer

    #include <stdio.h>
    int gcd(int, int);
    int main()
    {

        int a, b, result;
        printf("Enter the two numbers to find their GCD: ");

        scanf("%d%d", &a, &b);

        result = gcd(a, b);

        printf("The GCD of %d and %d is %d. ", a, b, result);

    }
  
    int gcd(int a, int b)
    {
    if ( a==0 ) return b;
    return gcd( b%a, a );
    }

Test Output for the recursive program:-
1280 ,198 - 2

197,13 -1

120,60 - 60

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.