代碼：

#include<iostream>
#include<cmath>
using namespace std;
int gcd(int, int);
int main()
{
cout << "用遞歸方式求最大公約數(shù)";                        
int a, b;

cout<<"請(qǐng)輸入a和b（>=0）:";

cin >> a>>b;

cout<<a<<"和"<<b<<"的最大公因數(shù)為：";

cout << gcd(a, b);
system("pause");
}
int gcd(int a, int b)                                //gcd:greatest common divisor，最大公因數(shù)的縮寫
{
if (b == 0)                               //遞歸結(jié)束的條件
return a;
else
return gcd(b, a%b);
}

算法分析：

用輾轉(zhuǎn)相除法求a,b兩個(gè)正整數(shù)的最大公因數(shù)。a與b的最大公因數(shù)，就是能同時(shí)整除a和b的最大整數(shù)。求a和b的最大公因數(shù)等價(jià)于求b與a%b的最大公因數(shù)，如此遞推，一直到a%b等于0為止，此時(shí)的a就是a和b的最大公因數(shù)。