Hey y’all, here is my code for the smallest common multiple. I am now changing this to instead be a loop, but I am just wondering why this doesn’t work. Was interested in trying it via recursion, so had gone this route.
If I’m understanding it correctly, it inevitably should work, but I’m guessing it is taking too much time. I’m instead going to craft a loop using similar language, but some comments would be appreciated. Many thanks!
function smallestCommons(arr) {
// Setting maximum value of the array
var max = arr.reduce(function (a, b) {
return Math.max(a, b);
});
// Setting minimum value of the array
var min = arr.reduce(function (a, b) {
return Math.min(a, b);
});
// function will constantly check all other necessary values against array's max
function recursiveSearch(multiple) {
var m = max - 1;
while (m >= min) {
if (multiple % m !== 0) {
return recursiveSearch(multiple + max);
}
else {
m--;
}
}
return multiple;
}
return recursiveSearch(max);
}
smallestCommons([1,10]);
check each multiple of max for divisibility by all numbers in the range - the multiple is increased if divisibility fails - the number is decremented if divisibility succeeds
this hews well to the definition of LCM as the lowest common multiple
it is a brute force or exhaustive algorithm - it is slow for couple reasons - if the range is large e.g. 2-10 then each multiple has to be checked many times - if the numbers are large like 18-20 then many multiples of max are tried before hitting a common multiple
still it can work iteratively in a loop
but as implemented recursively above it simply will not work for even slightly large numbers because each new multiple increases the recursion depth and javascript quickly runs out of memory after a certain recursion depth
technically both recursion and iteration are ways to repeatedly execute a block of code - the cost of recursion is much much higher in javascript and other procedural languages because a function call requires a lot of scaffolding to set up and tear down - one benefit of recursion sometimes is code can be much simpler and more compact than the iterative version
the most significant benefit of recursion however is not about code but for problem-solving - recursion as a problem-solving technique can be incredibly powerful - it can lead to breakthrough solutions that may be extremely hard to express without recursion
your code above uses recursion in a strict coding sense - it does not exhibit the hallmark of recursion used for problem-solving which is to use the solution for a certain “problem size” to generate a solution for a bigger “problem size”
There is definitely value in pushing yourself to find both the functional and iterative solution just as a mental exercise. Sometimes one is much more obvious or easy to implement than the other. When I researched how to find the least common multiple, the solution I found (on Wikipedia, I think) was inherently recursive, so I implemented that directly. (It had the added benefit of being broken into three mathematical concepts: least common multiple, smallest common multiple, and greatest common denominator.)
That solution (which I am by no means claiming is the best) is below, for the curious.
function smallestCommons(arr) {
arr.sort(function(a,b){
return a-b;
});
var smallest = arr[0];
var biggest = arr[1];
var least = lcm(smallest, smallest+1);
if (biggest - smallest === 1){
return least;
} else {
return lcm(least, smallestCommons([smallest+1, biggest]));
}
}
function lcm(a,b) {
return Math.abs(a*b)/gcd(a,b);
}
function gcd(a,b) {
if (b === 0){
return a;
} else {
a = a-b*(Math.floor(a/b));
return gcd(b,a);
}
}
strictly the recursive solution above is for gcd - it is useful since lcm can be reduced to gcd as explained here
another formulation of lcm is in terms of powers of prime factors - there may be recursive prime factorization algorithms - I don’t know one way or another