这个方法如何确定最大公约数？

Question

在数学中，两个或两个以上整数的最大公约数（gcd），当其中至少有一个不是零时，是除数字而没有余数的最大正整数。例如，8和12的GCD是4。维基百科

以下方法能够确定GCD：

def gcd(a, b)
  if a % b == 0
    b
  else
    gcd(b, a % b)
  end
end
p gcd(4, 12)
#=> 4

这种方法是如何工作的？

如果a%b==0那么b是可以同时进入a和b的最大数字。

但是为什么要再次调用相同的方法，但要切换参数，再次取模呢？

我不是在摸索其他部分背后的推理。

编辑：

添加一些put语句以使其更清晰：

def gcd(a, b)
  puts "Inside gcd, a: #{a}, b: #{b}, a \% b: #{a % b}"

  if a % b == 0
    puts "Inside if, a: #{a}, b: #{b}, a \% b: #{a % b}"
    b
  else
    puts "Inside else, a: #{a}, b: #{b}, a \% b: #{a % b}"
    gcd(b, a % b)
  end
end

p gcd(55, 105)

stdout：

Inside gcd, a: 55, b: 105, a % b: 55
Inside else, a: 55, b: 105, a % b: 55
Inside gcd, a: 105, b: 55, a % b: 50
Inside else, a: 105, b: 55, a % b: 50
Inside gcd, a: 55, b: 50, a % b: 5
Inside else, a: 55, b: 50, a % b: 5
Inside gcd, a: 50, b: 5, a % b: 0
Inside if, a: 50, b: 5, a % b: 0
5

Answer 1

关键的事实是，对于b的每一个除数g，我们有g除a当且仅当g除a%b（特别是，这对GCD适用）。这是由a=（a/b）*b a%b表示的，其中/是整数除法，因为g除以a（分别为a%b），而g除以b的所有倍数，包括（a/b）*b，因此g除以a%b（分别为a）。因此，如果递归调用终止，它会给出正确的结果，因为我们总是减少输入的大小（根调用除外）。

切换参数的原因是，较大的数字是第一个参数，因为0

Answer 2

这就是所谓的欧几里德算法。

为了理解为什么你需要交换数字并进行另一个递归调用，你需要理解它背后的实际数学是什么。看看这个YouTube视频，看看欧几里得算法是如何工作的。否则，我在下面写了我对算法的解释。

输入

• 两个正整数，a和b

输出

• a和b的最大公约数gcd

内部计算

• 如果一个

例如：

gcd(40,7)

40 = 7(5) + 5 
 7 = 5(1) + 2
 5 = 2(2) + 1 <-- your gcd
 2 = 1(2) + 0

但是，这意味着...

gcd(40,7) = gcd(7, gcd(40,7)) =
gcd(7, 5) = gcd(5, gcd(7, 5)) =
gcd(5, 2) = gcd(2, gcd(5, 2)) = 
gcd(2, 1) = 0

当gcd（a，b）=0时，b等于1，所以我们返回b

这是最重要的部分！如果我们不交换数字，我们就不能进行必要的数学运算，最终，跟踪b的位置，也就是我们的gcd。

因此，交换基本上是为了保持因素的正确性。试着在没有交换的情况下做数学题，你很快就会明白为什么它很重要；）

希望这有帮助！