C++最大公约数（递归）详解

gcd(x，y) = y; 如果y除以x而没有余数
gcd(x，y) = gcd(y, x/y的余数)；否则

这个定义指出，如果 x/y 没有余数，则 x 和 y 的最大公约数是 y；否则，答案就是 y 和 x/y 的余数的最大公约数。

下面的程序显示了递归的 C++ 实现：

// This program demonstrates a recursive function to

// calculate the greatest common divisor (gcd) of two numbers.

#include iostream 

using namespace std;

// Function prototype

int gcd(int, int);

int main()

 int num1, num2;

 cout Enter two integers: 

 cin num1 num2;

 cout The greatest common divisor of num1;

 cout and num2 is 

 cout gcd(num1, num2) endl;

 return 0;

int gcd(int x, int y)

 if (x % y == 0) //base case

 return y;

 else

 return gcd{y, x % y);

}

程序输出结果：

Enter two integers: 49 28
The greatest common divisor of 49 and 28 is 7

22166.html