在数学中，辗转相除法，又称欧几里得算法（英语：Euclidean algorithm），是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第 VII 卷，命题 i 和 ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

以上是 wikipedia 中的一段摘要，理论上欧几里得的辗转相除法实际可以计算任意多整数的最大公约数。

不过，今天主要是和大家分享一下其中一个最简单的案例，求两个整数的最大公约数。

根据 wikipedia 的解释，两个整数的最大公约数等于其中较小的数和两数的差的最大公约数，公式如下：

可能上面的描述不是很直观，那就用个例子来解释一下：

其实说白了就是不断的取余，直到余数为 0，就可以得出最大公约数了。

那么，能想到最直接的方式就是使用递归了，下面用Javascript实现一遍：