Question

Problem 1: Greatest Common Divisor (GCD) Please write two functions, g edi ) and gcdr , which both take two integers a, b and calculates their greatest common divisor (GCD) using the Euclidean algorithm gcdi () should do so using iteration while gcdr () should use recursion. Then write a third function, gcd(), which takes two integers a, band an optional third argument nethod which takes a charater string containing either "iterative" or "recursive", with a default value of "iterative", which calls either gedi) or gedr ) as appropriate. Euclidean Algorithm The Euclidean Algorithm hinges on the idea that the greatest common divisor of two numbers (a and b) is identically equal to the greatest common divisor of the smaller of the two mumbers (say b) and the difference of the two mumbers (a -b). That is to say ged(a, b)ged(b,a - b). For example: ged(27,21) 3 ged(21, 27 21) ged (21,6) 3 gol(6, 21 6) ged (15,6)3 ged(6, 15-6)ged(9,6) 3 ged (6,9-6) ged(6, 3) 3 ged(3,6-3) (1) (2) (3) (4) (5) (6) ged(3,3) 3 2 What's more, the GCD of two numbers (a and b) is identically equal to the greatest common divisor of the smaller of the two mumbers (say b) and the difference of the larger of the two mumbers (say a) and some integer q times the smaller. That is to say: ged (a, b)ged(b, a-qx b) Use this principle to guide your functions NOTE: We typically choose q to be as large as possible given the constraint a - q xb>0. HINT: ged(r, 0) r

Use R language to program

Answer 1

Program code:

# create gcd function with itration
gcdi <- function(a, b) {
while(b) {
t = b
b = a %% b # value a mod b then reminder save in b
a = t
}
return(a) # return gcd
}
# find gcd by recursive
gcdr <-function(a,b){
if(b==0){
return (a)
}

return(gcdr(b,a%%b)) #recursion used
}
#gcd function call gcd by itration and gcd by recursive
gcd<- function(a,b,sr){

if(sr=="recursive"){ #checking gcd by recursive
gcdr(a,b) #cal gcd recursive function
}
gcdi(a,b) # call gcd itration function
}

print("gcd 16 and 12 by itration : ")
print(gcd(16,12," ")) #print gcd by itration
print("gcd 27 and 21 by recursive ")
print(gcd(27,21,"recursive")) # print find gcd by recursive

r Code . create gcd function with itration gcdi<function (a, b) ( while (b) 1 2 - #value mod b then reminder save in b %% b 6 a-t 7 return(a) # return gcd 8 9 10 #find gcd by recursive gcdr <-function ( a, b) { if (b--0) return (a) 11 12 13 14 15 return (gcdr(b, a%%b ) ) 16 #recursion used 17 18 #gcd function call gcd by itration and gcd by recursive gcd<- function (a, b, sr) { 20 if (sr"recursive" ) { #checking gcd by recursive gcdr (a,b) #cal gcd recursive function 21 22 23 24 gcdi (a,b) # call gcd itration function 25 26 print ("gcd 16 and 12 by itration ") print(gcd(16, 12," ")) 29 print ("gcd 27 and 21 by recursive ") 30 print(gcd(27,21, "recursive")) 27 28 #print gcd by itration print find gcd by recursivel

Output:

[1] "gcd 16 and 12 by itration :" [1] 4 [1]"gcd 27 and 21 by recursive [1] 3

r Code . create gcd function with itration gcdi<function (a, b) ( while (b) 1 2 - #value mod b then reminder save in b %% b 6 a-t 7 return(a) # return gcd 8 9 10 #find gcd by recursive gcdr <-function ( a, b) { if (b--0) return (a) 11 12 13 14 15 return (gcdr(b, a%%b ) ) 16 #recursion used 17 18 #gcd function call gcd by itration and gcd by recursive gcd<- function (a, b, sr) { 20 if (sr"recursive" ) { #checking gcd by recursive gcdr (a,b) #cal gcd recursive function 21 22 23 24 gcdi (a,b) # call gcd itration function 25 26 print ("gcd 16 and 12 by itration ") print(gcd(16, 12," ")) 29 print ("gcd 27 and 21 by recursive ") 30 print(gcd(27,21, "recursive")) 27 28 #print gcd by itration print find gcd by recursivel

[1] "gcd 16 and 12 by itration :" [1] 4 [1]"gcd 27 and 21 by recursive [1] 3