find the greatest common divisor of a list of numbers in javascript

The greatest common divisor (GCD) of a list of numbers can be found using the Euclidean algorithm, which is based on the principle that the GCD of two numbers is the same as the GCD of the smaller number and the remainder of the larger number divided by the smaller number. This can be applied recursively to a list of numbers by repeatedly finding the GCD of the first two numbers in the list and replacing them with their GCD until only one number remains, which is the GCD of the original list.

Here's how to implement this algorithm in JavaScript using recursion:

index.tsx
function gcdList(numbers) {
  if (numbers.length == 1) {
    // base case: only one number, it is its own GCD
    return numbers[0];
  } else if (numbers.length == 2) {
    // base case: two numbers, find their GCD
    return gcd(numbers[0], numbers[1]);
  } else {
    // recursive case: split list and find GCD of first two numbers
    var splitIndex = Math.floor(numbers.length / 2);
    var left = numbers.slice(0, splitIndex);
    var right = numbers.slice(splitIndex);
    return gcdList([gcdList(left), gcdList(right)]);
  }
}

function gcd(a, b) {
  // Euclidean algorithm
  return b == 0 ? a : gcd(b, a % b);
}
620 chars
21 lines

This gcdList function takes an array of numbers as input and returns their GCD. It works by recursively splitting the list in half until it reaches a base case of either one or two numbers, at which point it either returns the number itself or calls the gcd function to find their GCD.

Here's how to use it:

index.tsx
var numbers = [12, 18, 24];
console.log(gcdList(numbers)); // output: 6
72 chars
3 lines

gistlibby LogSnag