RangeError: Maximum call stack size exceeded with recursion

Question

我正在尝试解决 Codewars 上的这个套路：https://www.codewars.com/kata/56e56756404bb1c950000992/train/javascript，我有一个我认为应该正确的方法，但它抛出一个 RangeError。这是我的代码：

function sumDifferencesBetweenProductsAndLCMs(pairs){
  return pairs.reduce((acc, curr) => {
    // LCM * GCD = product
    return acc + (curr[0] * curr[1] * (1 - 1 / GCD(curr)))
  }, 0)
}

function GCD(pair) {
  // Euclidean algorithm
  let a = Math.max(...pair);
  let b = Math.min(...pair);
  let r = a % b;
  if (r == 0) {
    return b;
  }
  return GCD([b, r]);
}

我哪里错了？我还能如何实现欧几里德算法？

Answer 1

我不确定我在这里得到了任何数学知识，但跳过零似乎可以阻止它永远递归。

任何 % 0 都会给出 NaN 并且可能任何 % NaN 都会给出 NaN 并且 NaN == 0 是错误的，所以如果你从零值开始进入 GCD 就没有办法了递归终止。

function sumDifferencesBetweenProductsAndLCMs(pairs){
  return pairs.reduce((acc, curr) => {
    // LCM * GCD = product
    if(Math.min(...curr) === 0) return acc; // Skip zeros
    return acc + (curr[0] * curr[1] * (1 - 1 / GCD(curr)))
  }, 0)
}

function GCD(pair) {
  // Euclidean algorithm
  let a = Math.max(...pair);
  let b = Math.min(...pair);
  let r = a % b;
  
  if (r == 0) {
    return b;
  }
  return GCD([b, r]);
}

console.log(sumDifferencesBetweenProductsAndLCMs([[15,18], [4,5], [12,60]]),840);
console.log(sumDifferencesBetweenProductsAndLCMs([[1,1], [0,0], [13,91]]),1092);
console.log(sumDifferencesBetweenProductsAndLCMs([[15,7], [4,5], [19,60]]),0);
console.log(sumDifferencesBetweenProductsAndLCMs([[20,50], [10,10], [50,20]]),1890);
console.log(sumDifferencesBetweenProductsAndLCMs([]),0);

RangeError: Maximum call stack size exceeded with recursion

RangeError: Maximum call stack size exceeded with recursion

javascript

recursion

callstack