使用递归可以计算两个数字的最大公约数。根据欧几里得算法，两个正整数 x 和 y 的最大公约数的计算方法如下:
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
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/tech/pnotes/22166.html