Finding the GCD and LCM (the Euclidean Algorithm)

In this lesson you'll use the Euclidean algorithm to find the greatest common divisor and least common multiple, experiencing the basics of recursive functions along the way. This is for people searching "JavaScript how to find the GCD" or "what is a recursive function."

The Euclidean algorithm is an ancient, efficient way to find the greatest common divisor (GCD) of two numbers. It repeats "divide the larger number by the smaller one and take the remainder, then do the same calculation again" until the remainder becomes 0. Writing a function this way — "calling itself over and over" — is called a recursive function.

The sample code has the gcd(a, b) function keep calling itself in the form gcd(b, a % b) until b === 0. Also check out the connection between the two algorithms: the least common multiple (LCM) can be found using the formula (a * b) / gcd(a, b), which relies on the greatest common divisor.

A common beginner stumbling block is that a recursive function absolutely must have an "ending condition." Without a termination condition like b === 0, the function would keep calling itself forever and cause an error. When writing a recursive function, get in the habit of first thinking through "what condition makes it end?"

This is a very commonly used subject for practicing recursive functions — a famous algorithm packed with fundamentals from both math and programming. Because the formula itself is simple, it's also an ideal introduction for learning to think in terms of recursive functions.