先上代码

int gcd(int a, int b)
{
return b ? gcd(b, a%b) : a;
}

辗转相除法是求两个数的最大公约数。例如 44 和 30
其核心思想为求44 与 30 的公约数转化为 求30 与 44%30 = 14 的公约数，如此一直递归（缩小规模），最后得到结果。
那么为什么这么转化是对的呢？
我们假设两个数的最大公约数为 k ，那么44 是k的倍数， 30 也是k的倍数，44%30 的结果也是k的倍数。
如果还觉得有些疑惑：对于44 % 30 我们可以看成 44 - 30 ，k的倍数减去k的倍数 = k的倍数。