What is GCD?

The GCD of two integers is the largest integer that can fully divide both numbers, without a remainder.

How to find GCD?

What is the greatest common divisor of 54 and 36?

The number $36$ can be expressed as a product of two integers in several different ways:

$ 36\times 1=18\times 2= 12\times 3 = 9\times 4$

Thus the divisors for $36$ are $1, 2, 3, 4, 6, 9, 12, 18, 36$

The number $54$ can be expressed as a product of two integers in several different ways:

$ 54\times 1=27\times 2= 18\times 3=9\times 6 $

Thus the divisors for $54$ are $1, 2, 3, 6, 9, 18, 27$

Common divisors are $1, 2, 3, 6, 9$ and $18$.

Greatest common divisor or GCD for $36$ and $54$ is $18$.

Problem Statement

Write a recursive function that computes the GCD of two integers.

Instructions

1. The function should take two integers, whose GCD is to be computed, as input.
2. The function should return the GCD of the two integers as output.
3. The function should be recursive.

Sample Input: 24, 18

Sample Output: 6