JavaScript 递归实现最大公约数 (欧几里得算法)

JavaScript 递归实现最大公约数 (欧几里得算法)

本文将使用 JavaScript 递归函数实现欧几里得算法（也称为辗转相除法）来求两个数的最大公约数。

算法原理

欧几里得算法的原理是：

1. 两个数中较大的数对较小的数进行取余运算。
2. 将较小的数替换成余数，较大的数替换成原来的较小的数。
3. 重复步骤 1 和 2，直到余数为 0，此时较小的数就是最大公约数。

例如：求 48 和 57 的最大公约数

• 57 % 48 = 9
• 48 % 9 = 3
• 9 % 3 = 0

因此，48 和 57 的最大公约数是 3。

代码实现

function gcd(num1, num2) {
  if (num2 === 0) {
    return num1;
  }
  return gcd(num2, num1 % num2);
}

// 测试
console.log(gcd(48, 57)); // 3

代码解释

• gcd(num1, num2) 函数接受两个参数 num1 和 num2，分别代表需要求最大公约数的两个数。
• 当 num2 为 0 时，num1 就是最大公约数，直接返回 num1。
• 否则，递归调用 gcd(num2, num1 % num2)，将 num2 和 num1 % num2 作为新的参数传入函数。

总结

本文介绍了使用 JavaScript 递归函数实现欧几里得算法来求最大公约数的方法，并提供了代码示例和解释。该方法简洁易懂，适合用于计算两个整数的最大公约数。