54. 【中学】求最大公约数——递归

54. 【中学】求最大公约数——递归

请使用递归算法计算正整数n和m的最大公约数GCD(n,m)。

　　          = m             当 m<=n 且 n mod m =0
GCD(N,M) = GCD(m,n)   当n<m时
                  = GCD(m, n mod m)     其他

输入：
        n和m

输出：
        n和m的最大公约数

【分析】：

他给的计算最大公约数的方法我没有看懂。不过高中数学有介绍过这相关的知识，可以用 更相减损之术 或 辗转相除法 来计算最大公约数

【代码】

#include <stdio.h>
int GCD(int n, int m);
int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	printf("%d\n", GCD(n,m));
}
int GCD(int n, int m)
{
	if (m == 0) return n;
	else {
		if (m <= n) return GCD(m,n%m);
		else return GCD(m,n);
	}	
}