递归函数来计算最大公约数

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)是一个无限循环，如果达到它。