Smallest Common Multiple recursive function taking forever

JavaScript
#1

Tell us what’s happening:
I’m trying to work on the Smallest Common Multiple challenge, and I’m so far hating the complexity and lack of practicality of it. I’m using a recursive function for this, and running my function with “big” (like 2 digit) numbers will create an infinite loop that freezes my browser.

console.log(JSON.stringify(
  smallestCommons([1, 5])
))

Would return 60 without problem, but doesn’t pass the test cases, because

console.log(JSON.stringify(
  smallestCommons([2, 10])
))

is holding it up with an infinite loop. Not fun.
Your code so far


function smallestCommons(arr) {
  const allBetweenArray =
    [...Array(Math.max(...arr) - Math.min(...arr) + 1)]
      .map((value, index) => Math.min(...arr) + index);
  const lcm = function leastCommonMultipleGivenArray(arr, initialLength) {
    return arr.find(
      (num, index, arrLevel2) =>
        arrLevel2.filter((numLevel2) => num === numLevel2)
          .length === initialLength
    ) || lcm(
      [
        ...arr,
        ...arr.slice(-1 * initialLength).map((num, index) => num + arr[index])
      ],
      initialLength
    );
  }
  return lcm(allBetweenArray.sort((a,b) => b- a), allBetweenArray.length);
}
console.log(JSON.stringify(
  smallestCommons([1, 5])
))

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/73.0.3683.86 Safari/537.36.

Link to the challenge:
https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/smallest-common-multiple/

#2

This is quite an odd way to approach the problem really, the time complexity is quite a bit larger than one would like,

in particular the arr.find call traverses the list in expected O(n), per element of the list leading to O(n^2), which if it doesn’t terminate adds another few O(n) operations and gets called again (which happens O(N) times where N is the correct result - if there’s a statistical relationship with n here I cba calculating it right now)

A word of caution, recursion isn’t always wise in JS, even though you’ve used the accumulating parameter tail form of the recursive call (there’s no tail call optimization in JS outside of Safari)

The slightly smarter way is to phrase this question in terms of a more simple one - the greatest common denominator, which has famously simple and elegant ways of finding it

#3

OK, I’ll try something with the GCD.

#4