A ima jos bolje resenje i zove se Euklidov algoritam.
Najlakse se pise rekurzijom i nema mnogo poziva, pa nema frke da ce da pukne stack.
Ideja je sledeca: najveci zajednicki sadrzalac za dva broja (u principu i za dva polinoma) je i najmanji zajednici sadrzalac za manji od njih i ostatak pri deljenju veceg manjim.
Znaci ako je a<b, onda je nzs(a,b)=nzs(b mod a, a);
Znaci, evo funkcije:
function Euclid(a, b: integer): integer;
begin
if a=0 then Euclid:=b
else Euclid:=Euclid(b mod a, a);
end;
Moras da pazis da je prvo mani broj kad pozivas f-ju, pa bi bilo korisno i
function nzs(a, b: integer): integer;
begin
if a<b then nzs:=euclid(a, b) else nzs:=euclid(b, a);
end;
gde ne moras da vodis racuna o redosledu.
Recimo za onaj primer od gore za 6 i 22 imas parove
6 i 22
4 i 6
2 i 4
0 i 2
10 BEGIN
20 HOME_SWEET_HOME
30 GOTO 20