# 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

- The function should take two integers, whose GCD is to be computed, as input.
- The function should return the GCD of the two integers as output.
- 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.