Výpočet největšího společného dělitele pomocí Euklidova algoritmu

eukliduv-algoritmus.md

#Euklidův algoritmus

Začnu tedy tím, co jsem se dočetla zajímavýho. 📖 Euklidův algoritmus byl napsán už asi 300 let př. n. l. a to panem matematikem Euklidem v knize Základy. Používá se pro výpočet největšího společného dělitele (greatest common divisor) přirozených čísel. Existuje taky Rozšířený Euklidův algoritmus, ale o tom zas jindy. Teď už matematika!

Příklad: Mám číslo 21 a 12

1. krok: 21 / 12 = 1 , zbyde 9
2. krok: 12 / 9 = 1, zbyde 3
3. 9 / 3 = 3, zbyde 0
4. společný dělitel čísel 12 a 21 je 3

Zkrátka dělíme zbytky, dokud nevyjde 0 a je to! 💡

A teď jak vypadá algoritmus přepsaný do Javascriptu, pokud hledáme společný dělitel pro dvě čísla, s použitím rekurzivní funkce:

var gcd = function(a, b) {  
    if ( ! b) {  
        return a  
    }  
  
    return gcd(b, a % b)  
};
console.log(gcd(21, 12));

Postup výpočtu pro čísla 21 a 12

1. pokud b == 0 vracím a
2. jinak: zavolám funkci gcd s argumenty b (tedy 12) a zbytkem po dělení obou čísel (operátor %), tedy 9
3. a znovu: b == 0 ? ještě ne, takže:
4. nyní mám tedy čísla 12 a 9, zavolám funkci s argumenty b 9 a zase zbytek po dělení = 3
5. to se opakuje, dokud b == 0, to znamená dokud zbytek nebude 0, dokud zkrátka nezbude nic!
6. nakonec se nám vypíše společný dělitel, v tomhle případě 3

Jak by vypadal test(y) pro takovou funkci? Stačí použít jednoduchý assert. Dává např. gcd(-21, -12) správný výsledek?
Jaký je rozdíl mezi var f = function() { ... } a function f() {...} ... tohle se netýká algoritmu ale JS jako takového.
Jak by vypadala nerekurzivní verze a obecně jaký je problém s rekurzí v jazycích jako Java, JS, C++ atd.