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.

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).u

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