Consider the following recursive algorithm intended to find the greatest common
ID: 664879 • Letter: C
Question
Consider the following recursive algorithm intended to find the greatest common divisor of nonnegative integers a and b with a < b.
procedure gcd(a, b : nonnegative integers with a < b) if a=0then
return b else
return gcd( b mod a, a ) end
(1) Trace the recursive calls when the input is a = 18, b = 45.
(2) What is/are the base case(s) of the recursive algorithm? Does
the procedure perform correctly in the base case(s)?
(3) Prove that any sequence of recursive calls terminates in a base
case.
(Note that b mod a is the remainder when b is divided by a.)
Explanation / Answer
(1)
Case when a=18, b=45:
The declaration of the function is as follows:
procedure gcd (a, b: non-negative integer with a<0)
a and b will be passed to the function.
a is not equal to 0, thus, it will not enter the given if condition.
In the else condition, it will return gcd(b mod a, a).
gcd(b mod a, a) = gcd(45 mod 18, 18) = gcd(9, 18)
Now, a = 9, b =18
a is not equal to 0. Thus, the recursive call will be made gcd(18 mod 9, 9)
gcd(18 mod 9, 9) = gcd(0, 9)
Here, a = 0, thus, it will return b that is equal to 9.
Thus, gcd(18, 45) = 9
Remainder
9
0
a
18
9
b
45
18
Total two recursive calls are made in the gcd(45, 18) and gcd(18, 9).
(2)
Base case:
Base case of the algorithm is when a = 0.
When a = 0, algorithm returns b. No recursive call is made.
Yes, it performs the algorithm correctly, because if one of the variable is 0 then there is no common divisor other than b.
(3)
Correctness:
When a < b
When a is 0, gcd(b, a) returns b as gcd this is the base case.
When a is not equal to 0, gcd(b, a) calls (b mod a) . Result of b mod a will be less than a and b. After that, a becomes b and the remainder becomes a, leading to smaller value of a as required by the algorithm.
Similarly, at each recursive call, remainder decreases finally to 0. Thus, after some recursive calls, algorithm terminates with a = 0 which is the base case.
Remainder
9
0
a
18
9
b
45
18