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]));

@trincot sorry i am new to javascript , so can i know what should i change to make it a good loop? — Ryan k
Why don't you look up Least Common Multiple (LCM)? The algorithm has been published so many times. — trincot
@trincot Please clarify why it's not a good loop, and how it could be improved. @Ryan k Welsome to Stack Overflow. I see you console.log() at the end there. Could you provide the current output and any errors in the console? — Axel Köhler
@trincot because i am doing freecodecamp javascript intermediate algorithm , so i am trying to do algorithm my self without copying other people algorithm. — Ryan k
@AxelKöhler the current output just show that the maximum call stack exceeded, but if i write console.log(smallestCommons[1,12]), it works. But then if i use numbers more than 12 it will show maximum call stack exceeded — Ryan k

trincot trincot · Accepted Answer · 2021-01-28T13:41:11

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

Maximum call stack exceeded error On function Find Small Common Multiple

1 Answers