C语言递归算法求最大公约数

#include <stdio.h>

int gys(int m, int n) { // 递归终止条件 if (n == 0) { return m; } else { return gys(n, m % n); // 递归调用 } }

int main() { int m, n; scanf('%d%d', &m, &n); printf('%d\n', gys(m, n)); return 0; }

递归法求最大公约数的思路是：假设a > b，则a和b的最大公约数g(a, b) = g(b, a mod b)，即b和a mod b的最大公约数。

具体实现时，当b为0时，a即为最大公约数。