用java的递归和非递归算法求最大公约数和最小公倍数

Question

如果r是a和b之间相除后的余数，则a和b之间的最大公约数与b和r之间的最大公约数相同，于是可以运用以下公式：gcd(a,b)=gcd(b,r)，例如：gcd(36,20)=gcd(20,16)=gcd(16,4)=gcd(4,0)，即当第二个数为0时，第一个数为最大公约数，于是36和20的最大公约数为4，运用递归和非递归算法编写gcd方法

Answer 1

非递归 :
int GCD1(int n, int m) {
if (n < m) swap(n, m);
while ((n % m) != 0) {
n=n%m;
swap(m, n);
}
return m;
}

递归:
int GCD2(int n, int m) {
if (n < m) swap(n, m);
if ((n % m) == 0) return m;
return GCD2(m,n%m);
}本回答被网友采纳