遞歸最大公約數解釋

Question

我發現這個解決方案：

function gcd_rec(a, b) { 
    if (b) { 
     return gcd_rec(b, a % b); 
    } else { 
     return Math.abs(a); 
    } 
} 

我試圖環繞它是如何工作的我的頭，我卡在第二行if (b) {

顯然它應該如果存在b，請通過函數（本身）運行？是真的？但是這一次運行時，它在那裏a現在的b和b價值是現在的a由b所得的餘數。

這是否意味着它永遠不會返回Math.abs(a)只要用戶將一個值b ???

有人可以解釋這樣對我？

Answer 1

我認爲維基百科解釋非常好：http://en.wikipedia.org/wiki/Greatest_common_divisor#Using_Euclid.27s_algorithm

要計算GCD（48,18），由18除以48得到的2商和12.其餘然後除以12 18得到的1商和6.剩餘然後除以6 12得到的餘數0，這意味着6是最大公約數。請注意，我們忽略了每個步驟中的商數，除非注意何時餘數達到0，表明我們已經到達答案。

所以，在你的算法中，b始終是前一個除法的餘數，以及前一個b。

如果b，新的餘數大於0，它將在if語句中返回true，因此我們忽略a並使用新輸入運行新算法。

Answer 2

每次調用遞歸函數時，都會傳入一個新值b（a % b）。所以當b達到0時，它會調用return Math.abs(a)。

Answer 3

這是Euclid's algorithm找到最大公約數。最後一個abs只是確保結果是非負的。