Question

5. The recursive algorithm given below can be used to compute gcd(a, b) where a and b are non-negative integer, not both zero.

Answer 1

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

The program implementation is given below and the output of the sample run is attached.

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)

#since it's a recursive function, it recalls the function with new parameters until a certain condition is satisfied

print(gcd(124, 244))

print()

#leaves a space after the first output

print(gcd(4424, 2111))

Learn more :brainly.com/question/25506437