Given two positive integers and , find their greatest common divisor (GCD), the largest number that divides both. For example, because divides both and , and no larger number does.
You could try every number from to and check which ones divide both. That works but is slow. There is a recursive solution that is clean and fast. Before reading on, think: what relationship might exist between and smaller inputs?
