Вітаю.
Знайшов такий код

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

Перевірив на папері, і бачу, шо працює, але не до кінця розумію, яка за цим логіка стоїть.

Наприклад, маємо 18 та 4. Той метод пошуку найбільшого дільника, який я розумію, це розклад чисел на множники, і пошук найбільшого спільного множника.

18 = 2 * 3 * 3
4 = 2 * 2

Найбільший спільний множник = 2, і воно й буде найбільшим спільним дільником для двох чисел. (я можу заплутатись в термінах трохи, але то таке).

Але код використовує ділення по модулю, тобто, воно повертає залишок від ділення.

18 % 4 = 2, бо 16 ділиться на 4, і залишається лише 2.

Далі йде 4 % 2 = 0, тобто, ми дійшли до кінця, і найбільшим спільним дільником є 2. Але чого воно працює?
**************************************

Поки що я розуміє наступне.

По-перше, якщо b % a = 0, то тут очевидно, що a є найбільшим спільним дільником, тому що воно ділиться на b, і саме на себе, якщо b < a, то % поверне b, котре =/= 0, і далі a та b міняються місцями.

Якщо b % a =/= 0, то це означає, що найбільший спільний дільник десь між 1 (включно) та a (не включно), і далі a - це залишок від ділення (котрий менший a), а b - це старе a (котре більше за залишок), і тепер ми намагаємось знайти найбільший спільний дільник між старим a, та залишок від ділення, котрий менший a.
***************************************

Чому в якості нового a ми використовуємо залишок від ділення, а в якості нового b - старе a ?