时间戳

首页 > 解决方案 > 尝试使用递归查找 LCM ......我得到无穷大

javascript - 尝试使用递归查找 LCM ......我得到无穷大

问题描述

编辑** 阅读我的问题，我现在意识到为什么我得到无穷大，num2 和 num1 永远不会相等，因为 num2 永远是一个更大的数字。是否可以使用递归来解决这个问题，还是使用循环之类的东西更好？我能够解决这个问题，只是对递归感到好奇。

如果两个数字相同，我应该已经找到 LCM 并希望将其退回。如果它们不相等，我将再次调用我的函数，但每次都增加其原始值。

 let leastCommonMultiple = (num1, num2) => {
    if (num1 === num2) return num1;

    return leastCommonMultiple(num1 + num1, num2 + num2)
}

console.log(leastCommonMultiple(4, 6)); // 12
console.log(leastCommonMultiple(3, 5)); // 15
console.log(leastCommonMultiple(2, 10)); // 10

标签： javascriptrecursion

解决方案

你当然可以写一个递归版本。这是一个特别不雅和低效的版本：

const lcm = (a, b, x = a, y = b) =>
  x == y 
    ? x 
    : x + a > y + b 
      ? lcm (a, b, x, y + b) 
      : lcm (a, b, x + a, y)

console .log (lcm (660, 126)) //=> 13860

我们分别使用xand作为andy的连续倍数，增加较小的一个，直到它与另一个一样大。当它们相等时，您就达到了 LCM。ab

稍加思考，我相信我们可以通过乘以正确的因素来提高效率。但我不确定当 GCD 如此简单高效地执行时，是否有任何充分的理由。

更新

这是一个更有效的版本：

const lcm = (a, b, x = a, y = b) =>
  x == y 
    ? x 
    : x > y 
      ? lcm (a, b, x, b * Math.ceil (x / b)) 
      : lcm (a, b, a * Math.ceil (y / a), y)

console .log (lcm (660, 126)) //=> 13860

这使用了与 GCD 使用的模运算符模糊相似的东西，找到一个值的第一个倍数至少与另一个值一样大。这应该是相对有效的。

更新 2

为了展示三元组是如何工作的，这是一个等效的更命令式的版本：

const lcm = (a, b, x = a, y = b) => {
  if (x == y) {
    return x
  } else {
    if (x > y) {
      return lcm (a, b, x, b * Math.ceil (x / b)) 
    } else {
      return lcm (a, b, a * Math.ceil (y / a), y)
    }
  }
}

console .log (lcm (660, 126)) //=> 13860

推荐阅读