Home > Blockchain >  Trying to find LCM using recursion...I get infinity
Trying to find LCM using recursion...I get infinity

Time:09-23

EDIT** Reading my question, I realize now why I get infinity, num2 and num1 will never be equal since num2 will always be a larger number. Is it possible to solve this using recursion or is it better to use something like a loop? I'm able to solve this, just curious about recursion.

If both numbers are the same, I should have found the LCM and want to return it. If they are not equal, I'll call my function again, but with each increased by its original value.

 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

CodePudding user response:

You certainly can write a recursive version of this. Here's one particular inelegant and inefficient version:

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

We use x and y as continuing multiples of a and b respectively, increasing the smaller one until it's as least as large as the other. When they're equal, you've hit the LCM.

With a little thought, I'm sure we could make this more efficient by multiplying the right factor. But I'm not sure there's any good reason for this when GCD is so straightforward to do efficiently.

Update

Here is a more efficient version:

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

This uses something vaguely analogous to the modulo operator you would use for GCD, finding the first multiple of one value at least as large as another. This should be relatively efficient.

Update 2

To show how the ternaries work, this is an equivalent more imperative version:

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

  • Related