JS – gcd modulo rec

Poznajemy optymalny sposób na wyliczenie największego wspólnego dzielnika przy pomocy modulo i rekurencji. Do dzieła.

Pomyślmy, liczba modulo przez liczbę daje 0 to mamy podzielność. Dobry warunek bazowy dla rekurencji:

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

Czyli tak, jak w b mamy mieć 0 to a ma nam zwrócić tę liczbę, która jest podzielna. Ok, matematyki nie będziemy odkrywać na nowo, tak wygląda ten algorytm:

function gcd(a, b){
    if(b == 0) 
        return a;

    return gcd(b, a % b);
  }


console.log(gcd(5,125)); //5
console.log(gcd(25,125)); //25

Czyli tak, 5 i 125. to weź 125 i 5 mod 125 (5). 5,5, to weź 5 i 5%5 (0). B równe zero, zwróć a (5).

Inny przykład, 6 i 16:

• a – 6, b -16
• 16, 6 mod 16 (10
• a 16, b 10
• 10, 16 mod 10 (6)
• a 10, b 6
• 6, 10 mod 6 (4)
• a6, b 4
• 4, 6 mod 4 (2)
• a 4 b 2
• 2, 4 mod 2 (0)
• a 2 b 0 zwróć a