Trace algorithm shown above when it finds gcd(13,20). That is, show all the steps used by the algorithm shown above to find gcd(13,20).

Question

1.   Trace algorithm shown above when it finds gcd(13 ,20). That is, show all the steps used by the algorithm shown above to find gcd(13 ,20).

procedure gcd(a ,b nonnegative integers with a>b)

if a=0 then return b

else return gcd (b mod a ,a)

{output is gcd(a, b) }

Answer 1

Here are the recursive calls

beginning with a=13 b=20

gcd(13,20)

gcd(7,13)

gcd(6,7)

gcd(1,6)

gcd(0,1)

returns 1