Question

Describe a recursive algorithm for computing the greatest

common divisor of two positive integers.

Short answer

The recursive algorithm to find the greatest common divisor of two positive integers is described.

Step-by-step solution

Describe recursive algorithm

The algorithm is recursive for a problem, if the algorithm is able to reduce the problem to a point where the input required to solve it is very small.

Describing the algorithm

Consider to find the greatest common divisor of two positive integers

Consider the algorithm gcd such that two positive numbers are and

The algorithm to find the greatest common divisor is as follows:

procedure gcd ( positive integers)

if a = 0 then return b

else return gcd (b mod a,a)

{output is (a,b) }

Hence, the recursive algorithm to find the greatest common divisor of two positive integers is described.