49 lines
791 B
C
49 lines
791 B
C
/*
|
|
* Author: Walter
|
|
* Student ID: 1930006025
|
|
* Week_1_Task_3
|
|
* Read in and compute the greatest common divisor (GCD) of
|
|
* two natural numbers using recursion
|
|
*/
|
|
|
|
#include <stdio.h>
|
|
#include <assert.h>
|
|
|
|
int GCD(int x, int y);
|
|
|
|
/* the real GCD function */
|
|
int _GCD(int x, int y);
|
|
|
|
int main() {
|
|
int x, y;
|
|
printf("Please input x\n");
|
|
scanf("%d", &x);
|
|
printf("Please input y\n");
|
|
scanf("%d", &y);
|
|
printf("Result is %d\n", GCD(x, y));
|
|
return 0;
|
|
}
|
|
|
|
int GCD(int x, int y) {
|
|
/* check x y are natural numbers */
|
|
assert(x >= 0);
|
|
assert(y >= 0);
|
|
|
|
/* make sure x >= y,
|
|
* then call the read GCD function */
|
|
if (x >= y) {
|
|
return _GCD(x, y);
|
|
} else {
|
|
return _GCD(y, x);
|
|
}
|
|
}
|
|
|
|
int _GCD(int x, int y) {
|
|
/* end of recursion */
|
|
if (y == 0) {
|
|
return x;
|
|
}
|
|
|
|
return _GCD(y, x % y);
|
|
}
|