Bài toán này thuộc dạng đệ quy tuyến tính.

Code:

#include <conio.h>
#include <iostream.h>
/*Ham tra ve Uoc chung lon nhat cua a va b*/
int UCLN(int a, int b){
   if(a==b)
      return a;
   else
   if(a>b)
      return UCLN(a-b,b);
   else
      return UCLN(a,b-a);
}
/*Chuong trinh chinh*/
void main(){
   clrscr();
   int a,b;
   cout<<"Nhap a = ";
   cin>>a;
   cout<<"Nhap b = ";
   cin>>b;
   cout<<"Uoc chung lon nhat cua "<<a<<" va "<<b<<" la "<<UCLN(a,b);
   getch();
}