I'm new to JavaScript and I'm learning about recursive functions. Specifically, I'm working on Euclid's algorithm. It all makes sense to me except for the base case on line 2 "if ( ! b) { return a; }. I understand that at some point a % b will be equal to NaN and this is when the recursive call should stop. But what does "if ( ! b)" mean in it's simplest form? I can't wrap my head around this. I appreciate the feedback in advance!
// Euclid's Algorithm
var gcd = function(a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
};
console.log(gcd(462, 910));
This is the rationale behind Euclid's algorithm.
gcd(a, b) = gcd(b, a%b)
But except when b
is 0. What is the result in this case? You can imagine that 0 has actually infinite factors in it: you can divide 0 by anything and the remainder will always be 0.
From this, we can derive that
gcd(a, 0) = a
And that's the stop case of the algorithm. if (!b)
is actually checking if b===0
, and returning a
in this case.
(! b) is evaluating the variable b to return the value of false. In JavaScript NaN is falsey which means it's not false, but it will evaluate to false in a Boolean evaluation.
As others have mentioned, the variable b will equal 0 and not NaN. I was just explaining how NaN evaluates for the sake of the original question.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With