# 欧几里得算法

也被称为：辗转相除法，其特征包括如下：

1. 有效性：辗转相除法 是一种有效的方法，能够找到两个整数的最大公约数
2. 递归性质：该算法可以通过递归方式实现，也可以用迭代方式
3. 基于整数除法：辗转相除法的核心操作是整数除法，通过计算余数和更新被除数，除数，直至余数为零，找到最大公约数

# 详细说明如下：

当我们有两个整数 p 和 q，我们可以使用欧几里得算法求它们的最大公约数 (GCD)。这个算法的基本思想是：

1. 若 q 为 0，则最大公约数为 p
2. 否则，将 p 除以 q 得到余数 r，然后用 q 代替 p，用 r 代替 q，重复上述过程

这个过程会一直持续，直到 q 变为 0，此时，p 的值就是最大公约数。这是一个反复取余的过程，逐步缩小问题规模。例如：

p = 48, q = 18

1. 48 / 18 = 2 余 12，此时 p = 18，q = 12
2. 18 / 12 = 1 余 6，此时 p = 12，q = 6
3. 12 / 6 = 2 余 0，此时 q = 0

最大公约数为 6。

在这个例子中，直到除数可以整数时的最大除数 就是 最大公约数，比如例子中的 12 / 6 = 2 余数为 0 是一个可以整数的除数 而且 也是唯一最大能整出的除数 所以 6 就是 最大公约数

# 使用 Java 语言描述

public static int gcd(int p, int q)

{

   if(q == 0) return p;

   int r = p % q;

   return gcd(q, r);

}

其中 q == 0 就直接返回 p 这是因为 0 不能除以任何数 所以 直接 返回 p 作为最大公约数

int r = p % q 就是取 被除数 和 除数 之间的余数

return gcd (q, r) 就是通过递归 逐步的缩小问题规模 得到最终的 最大公约数