Implementating the given algorithm in python 3, the greatest common divisors of <em>(</em><em>124</em><em> </em><em>and</em><em> </em><em>244</em><em>)</em><em> </em>and <em>(</em><em>4424</em><em> </em><em>and</em><em> </em><em>2111</em><em>)</em><em> </em>are 4 and 1 respectively.
The program implementation is given below and the output of the sample run is attached.
def gcd(a, b):
<em>#initialize</em><em> </em><em>a</em><em> </em><em>function</em><em> </em><em>named</em><em> </em><em>gcd</em><em> </em><em>which</em><em> </em><em>takes</em><em> </em><em>in</em><em> </em><em>two</em><em> </em><em>parameters</em><em> </em>
if a>b:
<em>#checks</em><em> </em><em>if</em><em> </em><em>a</em><em> </em><em>is</em><em> </em><em>greater</em><em> </em><em>than</em><em> </em><em>b</em>
return gcd (b, a)
<em>#if</em><em> </em><em>true</em><em> </em><em>interchange</em><em> </em><em>the</em><em> </em><em>Parameters</em><em> </em><em>and</em><em> </em><em>Recall</em><em> </em><em>the</em><em> </em><em>function</em><em> </em>
elif a == 0:
return b
elif a == 1:
return 1
elif((a%2 == 0)and(b%2==0)):
<em>#even</em><em> </em><em>numbers</em><em> </em><em>leave</em><em> </em><em>no</em><em> </em><em>remainder</em><em> </em><em>when</em><em> </em><em>divided</em><em> </em><em>by</em><em> </em><em>2</em><em>,</em><em> </em><em>checks</em><em> </em><em>if</em><em> </em><em>a</em><em> </em><em>and</em><em> </em><em>b</em><em> </em><em>are</em><em> </em><em>even</em><em> </em>
return 2 * gcd(a/2, b/2)
elif((a%2 !=0) and (b%2==0)):
<em>#checks</em><em> </em><em>if</em><em> </em><em>a</em><em> </em><em>is</em><em> </em><em>odd</em><em> </em><em>and</em><em> </em><em>B</em><em> </em><em>is</em><em> </em><em>even</em><em> </em>
return gcd(a, b/2)
else :
return gcd(a, b-a)
<em>#since</em><em> </em><em>it's</em><em> </em><em>a</em><em> </em><em>recursive</em><em> </em><em>function</em><em>,</em><em> </em><em>it</em><em> </em><em>recalls</em><em> </em><em>the function</em><em> </em><em>with </em><em>new</em><em> </em><em>parameters</em><em> </em><em>until</em><em> </em><em>a</em><em> </em><em>certain</em><em> </em><em>condition</em><em> </em><em>is</em><em> </em><em>satisfied</em><em> </em>
print(gcd(124, 244))
print()
<em>#leaves</em><em> </em><em>a</em><em> </em><em>space</em><em> </em><em>after</em><em> </em><em>the</em><em> </em><em>first</em><em> </em><em>output</em><em> </em>
print(gcd(4424, 2111))
Learn more :brainly.com/question/25506437
