java - 努力理解这段代码如何输出欧几里得算法

Question

我正在尝试编写 Euclids 算法的代码，我在网上找到了一些代码，可以计算出输入的两个数字的最大公约数。在这里

else {
    return gcd(b, a % b);
}

但是，我不太明白它是如何让我成为最大公约数的。我了解欧几里得算法在纸上是如何工作的，但不是这个。 在我看来，上面的代码应该返回 b 的模数 a，所以如果“a”是 1071，“b”是 462，它将返回 147，但是上面的代码返回 21。<code>gcd(b, a % b); 中的第一个 b影响输出？

完整代码如下:

package algorithms;
import java.util.Scanner;
public class Question3 {
    private static Scanner input=new Scanner(System.in);
    public static void main(String[] args) {


    //simple input statements to get the numbers of the user
    System.out.print("Please input the first number to be worked on= ");
    double a=input.nextDouble();
    System.out.print("Please input the second number to be worked on= ");
    double b=input.nextDouble();

    //call the method in which the calculations are done
    double commondiv=gcd(a,b);


    //print out the the common divisor
    System.out.print("The Common Divisor of "+ a +" and "+ b + " is "+commondiv);
    //System.out.print(b);
}
public static double gcd(double a, double b){
    //an if statement will allow for the program to run even if
    //a is greater than b
    if (a>b){
        //if the input b is equal to zero
        //then the input a will be returned as the output
        //as the highest common divisor of a single number is itself
        if (b == 0){

            return a;
        }
        //this returns the greatest common divisor of the values entered
        else{
            return gcd(b, a % b);
        }
    }
    else if (a<b){
        if (a == 0){

            return b;
        }
        else{
            return gcd(a, b % a);
        }

    }
    return 0;
}

Answer 1

请参阅以下迭代说明:

第一次迭代
a = 1071 和 b = 462

1. a >b 所以
   gcd(b,a % b) 即 gcd(462,147)

2. 同样 a>b 为真，因为 a = 462，b = 147 所以
   gcd(147,21)

3. a>b 为真，因为 a = 147，b = 21 所以
   gcd(21,0)

4. a>b 为真，因为 a = 21 ,b = 0 现在 b == 0 是真的 返回 a 即 21