javascript - 超出最大调用堆栈错误在函数上查找小公倍数

Question

我正在尝试构建一个函数来查找范围内数字的最小公倍数。例如，如果我通过 minimumCommons([1,3])，找到 1 和 3 的最小公倍数，它也可以被 1 和 3 之间的所有数字整除。 这里的答案是 6。
我使用递归来找到最小公倍数，但是如果我传递数字大于 12 的数组的第二个索引，它将输出超过最大调用堆栈

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

Answer 1

您的递归算法将不得不检查大量系数，因此您遇到堆栈溢出错误也就不足为奇了。
要查找数字列表的最小公倍数，您可以使用以下规则:您可以用它们的最小公倍数替换该列表中的任何对，然后从那里继续。通过这种方式，您可以逐步减少列表，直到剩下一个值。
实际上，不需要真正创建该列表。您可以根据上述原则从最小值到最大值迭代值并累积最小公倍数:

// 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