遞歸函數來計算最大公約數

Question

我想實現一個遞歸函數來計算兩個數字的gcd，但我的代碼不工作，任何想法有什麼不對？

public static int gcd(int a, int b) { 
    if (a == b) { 
     return a; 
    } 

    while (a != b) { 
     if (a > b) { 
      gcd(a - b, b); 
     } else if (b > a) { 
      gcd(a, b - a); 
     } 
    } 
    return a; 
} 

Answer 1

如果您使用遞歸，則不需要while循環。只要做到：

public static int gcd(int a, int b) { 
    if (a == b) { 
     return a; 
    } 

    if (a > b) 
     return gcd(a - b, b); 

    return gcd(a, b - a); 
} 

順便說一句，while (a != b)是一個無限循環，如果達到它。