CIT239 Java Programming Lab 18a Recursive GCD This lab exercise is taken from Exercise 18.3 ofthe Liang textbook. Due Date You must demonstrate the solution for this lab exercise to the instructor by Sunday, May 7, 2017, in order to receive credit for this work. Compute Greatest Common Divisor using Recursion In class we discussed a "brute force" method of computing Greatest Common Divisor (GCD), as well as a recursive algorithm, known as Euclid'sAlgorithm, which is stated below: If m and n are positive integers, ged(m, n can be defined as follows: If m%n s 0, then ged(m,n) is n. Otherwise, ged(m,n) is ged(n, m%n). Write a recursive method to find the GCD, using Euclid's Algorithm. Write a test program that accepts two integer inputs and displays their GCD. Include an interactive outer loop that allows the user to repeat the process for other numbers Instrumenting the Code We have seen before that adding print statements at key locations in a program can help illustrate exactly how that program works. At the entry point of the gcd method, add a statement to output the calling parameters m and n. This will allow you to see how many times the recursive method was called, and what the calling parameters were Before each return from the gcd method, add a statement to output the returned value, as well as the input parameters which were used for that particular invocation of gcd. (Also indicate whether this return is from a "base case" or a "recursive case".) Sample output The following text shows examples of computing the GCD for various integers: run, Enter two integers (or 'q' to exit) 511 22 Entering 'gcd' method m 511 n 22 Entering 'gcd' method. 22 n 5 Entering 'gcd' method m 5, n Entering 'gcd' method m 2, n Returning 'gcd value 1 BASE CASE m 2, n 1 Returning 'gcd' value 1 recursive case m 5, n 2) Returning 'gcd' value 1 recursive case ma 22, n 5) Returning 'gcd' value 1 recursive case m 11 n 22 The GCD of 511 and 22 is 1. CIT239 SU Lab18a ve GCD 20170416 docx. 4/15/2017 8:25 PM page 1 of 2