โปรแกรม C หา GCD ด้วยฟังก์ชันเรียกซ้ำ (Recursive)

โจทย์

หาตัวหารร่วมมาก (GCD) ของสองจำนวนโดยใช้ฟังก์ชันเรียกซ้ำ (recursive) ในภาษา C

วิธีแก้

อัลกอริทึม

ขั้นตอน 1 - กำหนดฟังก์ชันเรียกซ้ำ

ขั้นตอน 2 - อ่านจำนวนเต็ม a และ b

ขั้นตอน 3 - เรียกฟังก์ชันเรียกซ้ำ

a. ถ้า i > j
b. คืนค่าฟังก์ชันพารามิเตอร์ i,j
c. ถ้า i == 0
d. คืนค่า j
e. ไม่เช่นนั้น คืนค่าฟังก์ชันพารามิเตอร์ i, j%i

Flowchart

มีแผนภาพ flowchart สำหรับอัลกอริทึมหา GCD แบบ recursive

ตัวอย่าง

โปรแกรม C หา GCD ด้วยฟังก์ชัน recursive:

#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); }

ผลลัพธ์

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