Biegral Blog

#include<iostream>
using namespace std;

int gcd(int x, int y)
{
	if(0 == y)
		return x;

	return gcd(y, x % y);  //注意，此处gcd中的参数不能颠倒位置，否则是“死”递归
}

int main()
{
	cout << gcd(12, 16) << endl;
	cout << gcd(16, 12) << endl;

	cout << gcd(2012, 2102) << endl;

	return 0;
}

 另外给出两种常见的求gcd的方法：

#include<iostream>
using namespace std;

int gcd(int x, int y)
{
	int tmp;
	while(y)
	{
		tmp = x % y;
		x = y;
		y = tmp;
	}

	return x;
}

int main()
{
	cout << gcd(0, 0) << endl;
	return 0;
}

#include<iostream>
using namespace std;

int gcd(int x, int y)
{
	//千万不要忽略对0的判断，否则有bug
	if(0 == x)
		return y;
	if(0 == y)
		return x;

	while(x != y)//欧几里德算法
	{
		if(x > y)
			x -= y;
		else
			y -= x;
	}

	return x;
}

int main()
{
	cout << gcd(16, 0) << endl;
	return 0;
}