在 JAVA 中使用递归解释最大公约数

Question

我正在努力更好地理解递归。如果我理解正确，递归适用于您的基本案例和原始案例的更简单版本。所以通常人们会看到代码从参数中减去一个。但是，我看到了下面的代码，如果不简化案例，我不明白它是如何工作的。任何解释都会有所帮助。

public static long gcd(long a, long b) {

   if (b==0) 
     return a;
   else
     return gcd(b, a % b);
 }

Answer 1

我理解递归的最简单方法是用几个例子构建递归树

gcd(10,20) ------------------ output: 最后这里返回10.
|
gcd(20, 10)-------------------- output: 由于输出没有发生其他任何事情，10 在这里向上传播并返回到上面的语句。
|
gcd(10, 0) ------------------ 输出： 这是基本情况，返回 10。

gcd(4,5)-------------------- output: 最后这里返回1.
|
gcd(5, 4)-------------------- output: 与下面相同，1 传播回执行链
|
gcd(4, 1)-------------------- output: 由于输出没有发生其他任何事情，因此 1 在这里向上传播并返回到上面的语句。
|
gcd(1, 0)--------------------输出： 这是基本情况，其中返回 1。

gcd(8,12)-------------------- 输出： 最后这里返回4.
|
gcd(12, 8)-------------------- output: 与下面相同，4 传播回执行链
|
gcd(8, 4)-------------------- output: 由于输出没有发生其他任何事情，因此 4 在这里向上传播并返回到上面的语句。
|
gcd(4, 0)--------------------输出： 这是基本情况，返回 4。

运行通过这样的例子帮助我理解了递归递归关系，它呈现了递归方法的本质。

注意：对于树上可怕的格式感到抱歉。我不是 SO 专家，也不知道如何让这些 "trees" 看起来更好。

Answer 2

此特定示例使用 Euclidean algorithm。它指出，您可以通过取第二个数字并将其作为第一个数字并取 a/b 的余数来获得第二个数字来找到该值的 gcd。您继续这样做，直到第二个数字达到 0。

例子 gcd(2,8)

a=2
b=8
a%b=2

所以下一个电话是gcd(8,2)

a=8
b=2
a%b=0 (since 8/2=4)

所以它会在剩余时间调用 gcd gcd(2,0)

a=2
b=0

它将达到 b==0 和 return a=2 的基本情况。

Answer 3

我真的不明白你所说的简化案例是什么意思，但让我试着解释一下那里发生了什么。您的基本情况是：
如果（b==0） return一个；

一般来说，当我们谈论递归时，我们需要做的第一件事就是找到基本情况。好吧，一个数字和一个 0 的 gcd 总是数字（我们的基本情况）。

接下来我们要说一下%是做什么的。 5%10 = 5 和 10%5=0。那么让我们举个例子。 gcd(5,10)

gcd(10, 5%10) = gcd(10,5)
gcd(5, 10%5) = gcd(5,0)
当它到达第三次递归时，它命中基数 class 和 returns 5.

我们可以将基本情况设为如果（a==0||b==0） return a+b;

所以当你说 return gcd(a,b) 时，该方法会再次启动并执行它的工作，直到它 return 很长。

嗨。谢谢

在 JAVA 中使用递归解释最大公约数

Explaining greatest common divisor using recursion in JAVA

java

recursion