Question

The recursive algorithm given below can be used to compute gcd(a, b) where a and b are non-negative integer, not both zero. procedure gcd(a, b) if a > b then gcd(a, b) := gcd(b, a) else if a = 0 then gcd(a, b) := b else if a = 1 then gcd(a, b) := 1 else if a and b are even then gcd(a, b) := 2gcd(a/2, b/2) else if a is odd and b is even then gcd(a, b) := gcd(a, b/2) else gcd(a, b) := gcd(a, b − a) Use this algorithm to compute (a) gcd(124, 244) (b) gcd(4424, 2111).

Answer 1

Coding the given algorithm in python 3, the greatest common divisor of the values (124 and 244) and (4424 and 2111) are 4 and 1 respectively.

The program implementation goes thus :

def gcd(a, b):

#initialize a function named gcd which takes in two parameters

if a>b:

#checks if a is greater than b

return gcd (b, a)

#if true interchange the Parameters and Recall the function

elif a == 0:

return b

elif a == 1:

return 1

elif((a%2 == 0)and(b%2==0)):

#even numbers leave no remainder when divided by 2, checks if a and b are even

return 2 * gcd(a/2, b/2)

elif((a%2 !=0) and (b%2==0)):

#checks if a is odd and B is even

return gcd(a, b/2)

else :

return gcd(a, b-a)

A sample run if the program on the values given :

print(gcd(124, 244))

print()

#leaves a space after the first output

print(gcd(4424, 2111))

Learn more :brainly.com/question/25506437