Smallest Common Multiple & GCD

So I created this code using some formulas that I found on math websites to efficiently find the greatest common divisor and then using that to find the LCM of a range of numbers. When I execute the “Run the Tests” button, the console is returning “Maximum call stack size exceeded.” I’m not sure why I am getting this. Any help would be much appreciated.

Your code so far


function findGCD(a, b) {
    let nextLoop = [];
    if (a % b !== 0) {
      nextLoop.push(b);
      nextLoop.push(a % b);
      findGCD(nextLoop)}
    else if (a % b == 0) {
      return b;}  
    
} 

function smallestCommons(arr) {
  let newArray = [];
  let mapArray = arr.map(item => newArray.push(item));
  let sortArray = newArray.sort();
  let rangeArray = [];
  for (let i = newArray[0]; i <= newArray[1]; i++) {
    rangeArray.push(i);
  }
  
 let reduceArray = rangeArray.reduce((accumulator, currentValue) => {findGCD(accumulator, currentValue)});
 let multArray = rangeArray.reduce((accumulator, currentValue) => accumulator * currentValue);
 return multArray / reduceArray;
}

smallestCommons([5,1]);

Your browser information:

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

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

Did you Google “Maximum call stack size exceeded” to see what it means and why you would possibly be getting that message?

There are quite a few things you need to clean up here.

This, though is very wrong:

function findGCD(a, b) {
    let nextLoop = [];
    if (a % b !== 0) {
      nextLoop.push(b);
      nextLoop.push(a % b);
      findGCD(nextLoop)}
    else if (a % b == 0) {
      return b;}  
}

It’s not going to work. The function takes two arguments (both numbers). What happens when you run the function is:

Say those arguments are 1 and 2

1 % 2 is 1
1 != 0, so
Call function again like findGCD([2, 1])
a is now an array instead of an integer, and no second argument is passed, so b is undefined.
[2,1] % undefined is NaN
NaN != 0
Call function again like findGCD([undefined, NaN])
[undefined, NaN] % undefined is NaN
NaN != 0
And so on, infinite loop

Note that even if you fix this, recursion is not generally a good thing to use for these challenges, it is not optimised at all in JS, and these challenges need to run quickly

findGCD is a recursive function, but it’s not written properly. For one, it’s defined to have two parameters a and b, but in the subsequent calls to it, it’s given a single array instead. You don’t need that array; just pass b and a % b directly to findGCD.

Another thing. Since this recursive function returns a value, the inner calls to findGCD must be returned as well. Otherwise any computed value you might have just gets thrown away.

return findGCD(b, a % b);

Another problem point is that in the reduce call that uses the GCD function, you’re using an arrow function with braces. That makes it require an explicit return, or it will just return undefined, which is what your code does. Your GCD function then receives undefined inside reduce, but it doesn’t know how to handle it and continues to call itself nonstop until it hits the same error.

1 Like

Thanks. That was very helpful. I also realized that I didn’t have a clear understanding of the math behind LCM and GCD, but now I got it!

function findGCD(a, b) {
    if (a % b !== 0) {
      return findGCD(b, a % b)}
    else if (a % b == 0) {
      return b;}  
    } 
function smallestCommons(arr) {
  let rangeArray = [];
  for (let i = Math.max(arr[0], arr[1]); i >= Math.min(arr[0], arr[1]); i--){
    rangeArray.push(i);
  }
 return rangeArray.reduce((accumulator, currentValue) => accumulator * currentValue / findGCD(accumulator, currentValue))
}

console.log(smallestCommons([2, 10]));type or paste code here

I