Как работает ли алгоритм Евклида?

Я только что нашел этот алгоритм для вычисления наибольшего общего делителя в своих конспектах лекции:

public static int gcd( int a, int b ) {
    while (b != 0) {
        final int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Таким образом, r - это остаток при делении b на a (получить мод). Затем b присваивается a , а остаток присваивается b , и возвращается a . Я хоть убей не могу понять, как это работает!

И затем, очевидно, этот алгоритм работает не для всех случаев, и тогда нужно использовать этот:

public static int gcd( int a, int b ) {
    final int gcd;
    if (b != 0) {
        final int q = a / b;
        final int r = a % b; // a == r + q * b AND r == a - q * b.
        gcd = gcd( b, r );
    } else {
        gcd = a;
    }
    return gcd;
}

Я не понимаю причин, лежащих в основе этот. Обычно я получаю рекурсию и хорошо разбираюсь в Java, но это ускользает от меня. Помогите, пожалуйста?