Chương trình C để tìm GCD của các số bằng cách sử dụng hàm đệ quy

Vấn đề

Tìm ước số chung lớn nhất (GCD) cho hai số đã cho bằng cách sử dụng hàm đệ quy trong ngôn ngữ lập trình C.

Giải pháp

Giải pháp để tìm ước số chung lớn nhất (GCD) cho hai số đã cho bằng cách sử dụng hàm đệ quy như sau -

Thuật toán

Tham khảo thuật toán đưa ra bên dưới để tìm ước số chung lớn nhất (GCD) cho hai số đã cho bằng cách sử dụng hàm đệ quy.

Bước 1 - Định nghĩa hàm đệ quy.

Bước 2 - Đọc hai số nguyên a và b.

Bước 3 - Gọi hàm đệ quy.

a. if i>j
b. then return the function with parameters i,j
c. if i==0
d. then return j
e. else return the function with parameters i,j%i.

Lưu đồ

Dưới đây là một sơ đồ cho thuật toán tìm ước số chung lớn nhất (GCD) cho hai số đã cho bằng cách sử dụng hàm đệ quy.

Ví dụ

Sau đây là chương trình C để tìm ước chung lớn nhất (GCD) cho hai số đã cho bằng cách sử dụng hàm đệ quy -

#include<stdio.h>
#include<math.h>
unsigned int GCD(unsigned i, unsigned j);
int main(){
   int a,b;
   printf("Enter the two integers: \n");
   scanf("%d%d",&a,&b);
   printf("GCD of %d and %d is %d\n",a,b,GCD(a,b));
   return 0;
}
/* Recursive Function*/
unsigned int GCD(unsigned i, unsigned j){
   if(j>i)
      return GCD(j,i);
   if(j==0)
      return i;
   else
      return GCD(j,i%j);
}

Đầu ra

Khi chương trình trên được thực thi, nó tạo ra kết quả sau -

Enter the two integers: 4 8
GCD of 4 and 8 is 4