欧几里得算法 - JavaScript

Question

我是JavaScript的新手，正在学习递归函数。具体而言，我正在研究欧几里得算法。除了第2行的基本情况"if ( ! b) { return a; }"外，其他都很清楚。我知道在某个时候a % b将等于NaN，这就是递归调用应该停止的时候。但是"if ( ! b)"在最简单的形式下是什么意思？我无法理解这一点。提前感谢您的反馈！

// Euclid's Algorithm 

var gcd = function(a, b) {  
   if (!b) {  
       return a;  
   }  

   return gcd(b, a % b);  
};  
console.log(gcd(462, 910));

- CTK

---

你可以在这里找到一些相关信息：http://www.codeproject.com/Articles/182416/A-Collection-of-JavaScript-Gotchas#nullundefined - higuaro

在那篇文章之后，你可以在这里找到很多信息 https://dev59.com/42Ij5IYBdhLWcg3w04Xd - higuaro

谢谢您提供的资源！ - CTK

Answer 1

这是欧几里得算法背后的原理。

gcd(a, b) = gcd(b, a%b)

但是当b为0时除外，这种情况下的结果是什么？你可以想象0实际上具有无限的因数：你可以用任何数除以0，余数总是0。

由此，我们可以得出结论：

gcd(a, 0) = a

这就是算法的停止情况。 if (!b) 实际上是检查是否 b===0，并在这种情况下返回 a。

- Juan Lopes

Answer 2

(! b) 用于对变量b进行求值，返回false的值。在JavaScript中，NaN是falsey，这意味着它不是false，但在布尔求值中它会被视为false。

正如其他人所提到的，变量b将等于0而不是NaN。我只是为了解答原问题而解释了NaN的求值方式。

- Nimix

---

事实上，Nimix，尽管你的两个句子都是正确的，但第二个句子是无关紧要的，因为当b达到零时它并不会变成NaN，而是在那一步停止。 - paxdiablo

Answer 3

欧几里得算法的基本情况是当其中一个参数等于零时，这意味着两个数的最大公约数是非零数。您可以参考此链接查看一些示例： https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm 以下是我如何实现欧几里得算法：

   function gcd(a, b) {
        // base cases
        if(a === 0) { return b;}
        if(b === 0) { return a;}

        // decrease and conqure - recursion
        return gcd(b, a % b);
    }

    console.log(gcd(9, 6));
    console.log(gcd(6, 9));

- MissDesire

Answer 4

简单来说，在这种情况下，!b 和 b == 0 是一样的。零作为真实值为假，所以!0将是真的。

换句话说，当b为零时，该函数返回a，否则它将继续通过更多递归级别。

你认为a％b会变成NaN，其实是错误的-事实上，b变成零，并且你检测到了这一点，这意味着你实际上从未通过除以零得到NaN。

- paxdiablo

Answer 5

//I'm glad that I can help others, here is my version:
//Euclid's algorithm:
//1)Find reminder of division m by n
//2)If remainder is zero, n is a solution
//3)Reduce(if r != zero)
const euclid = function(num1, num2){
    //compute the remainder:
    var remainder = num1 % num2;
    if(remainder == 0){
        return num2;
   
    }else{
        //step 3:
        num1 = num2;
        num2 = remainder;
       return euclid(num1, num2);
    }
}
//test the result:

console.log(euclid(80, 30));

- YouKnowWho

---

欢迎来到StackOverflow！感谢您的回答。为了使答案更好，请添加一些解释，说明您认为这可能是对其他答案的改进。此外，如果num2为零会发生什么（以及您认为应该发生什么）？ - Scott Sauyet