# Challenge 1: Find the greatest common divisor

In this lesson, the user will find the greatest common divisor (GCD) using recursion.

We'll cover the following

# 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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.