javascript - Maximum call stack exceeded error On function Find Small Common Multiple

Question

I am trying to build a function to find the smallest common multiple by numbers in range. For example if i pass smallestCommons([1,3]), find the smallest common multiple of both 1 and 3 that is also evenly divisible by all numbers between 1 and 3. The answer here would be 6.

I use the recursion to find the Smallest Common Multiple, but if i pass the second index of array with number more than 12 than it will output maximum call stack exceeded

function smallestCommons(arr) {
  arr.sort((a,b) => b - a);
  let newArr = [];

  for(let i = arr[0]; i >= arr[1]; i--) {
    newArr.push(i);
  }
  
  function findCommon(multiples) {
    let currentValue = newArr[0] * multiples;
    if(newArr.every(item => currentValue % item == 0)) {
      return currentValue;
    } else {
      return findCommon(multiples + 1);
    }
  }

 return findCommon(1);
}

console.log(smallestCommons([1,13]));

question from:https://stackoverflow.com/questions/65937510/maximum-call-stack-exceeded-error-on-function-find-small-common-multiple

Answer 1

Your recursive algorithm is going to have to check a whole lot of coefficients, and so it is no surprise you bump into a stack overflow error.

For finding the least common multiple of a list of numbers, you can use the rule that you can replace any pair in that list with their least common multiple and continue from there. This way you reduce the list step by step until you have one value left.

And actually, it is not needed to really create that list. You can just iterate the values from minimum to maximum and accumulate the least common multiple according to the above principle:

// Euclid's algorithm
function gcd(a, b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

function lcm(a, b) {
    return a * b / gcd(a, b);
}

// lcm of all numbers in the range [a, b]:
function lcmOfRange(a, b) {
    let result = a;
    for (let i = a + 1; i <= b; i++) {
        result = lcm(result, i);
    }
    return result;
}

// lcm of all numbers in the range [min(arr), max(arr)]
function lcmOfMinMax(arr) {
    return lcmOfRange(Math.min(...arr), Math.max(...arr));
}

console.log(lcmOfMinMax([1, 3])); // 6
console.log(lcmOfMinMax([1, 13])); // 360360