#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
/[highlight=red:eb294d9f30]*3．45整数x和y的最大公约数是x和y能够整除的最大整数。编写一个递归函数gcd，
返回整数x和y的最大公约数。整数x和y的最大公约数的递归定义如下：如果y等于0，
则gcd(x，y)为x，否则gcd(x，y)为gcd(y，x％y)，其中％是求模运算符。[/highlight:eb294d9f30]
*/
int gcd(int,int);
int main()
{
int x,y;
cout<<"x=";
cin>>x;
cout<<endl<<"y=";
cin>>y;
cout<<endl<<"最大公约数为:"<<gcd(x,y)<<endl;
char quit;
cout<<"quit?yes or no";
cin>>quit;
if(quit='q')
return 0;
}
int gcd(int q,int p)
{
for(int i=q;i>=1;i--)
if(q%i==0&&p%i==0)
return i;
}

最大公约数是求出来了，我总觉得他题目的意思不是这么做的；
请教一下该如何做？

递归的意思是如果满足某种条件，就再次调用函数本身；否则就返回结果。

那就是切题了，是吧！

其实这里已经把算法说出来了。照书的方法，我想应该是这样：

gcd(a, b) = gcd(b, a mod b) if a mod b != 0
= b if a mod b == 0
根据这个写吧

谢了；
确实是说出来了，仔细体会一下，挺巧妙的；
不过，我的方法也能解决问题，为什么要弄得那么复杂呢。

因为要减小运行时间。同样大的两个数字求公约数，你的方法比这个更巧妙的方法需要更多的运行时间，而且是多得多。

要不要再来一次求GCD的时间复杂度

呵呵，明白了；
谢谢大家！