{BEGIN:  EUCLIDR.TXT        4 18-Dec-85    16   512  Textfile }
PROGRAM Euclid;

  {This programs uses Euclid's method to determine the greatest common
   divisor of two integers using a recursive algorithm.

   efg, 18 December 1985.
   See p. 19 of "Fundamentals of Computer Algorithms", Horowitz and Sahni.

   Sample Data:
     Input:  1128 1272     Output:  24  }

  VAR
    x,y:  INTEGER;


  FUNCTION gcd(a,b:  INTEGER):  INTEGER;
    VAR
      t:  INTEGER;
  BEGIN
    IF   b = 0
    THEN gcd := a                 // use RESULT := a in Delphi (efg, Oct 2000)
    ELSE gcd := gcd(b, a MOD b)   // use RESULT := gcd(b, a MOD b)
  END {gcd};

BEGIN
  REPEAT
    WRITELN ('Enter two numbers (0s to quit):  ');
    READLN (x,y);
    IF   (ABS(x) > 0) AND (ABS(y) > 0)
    THEN WRITELN ('Greatest common divisor for ',x,' and ',y,' is ',gcd(x,y))
  UNTIL (x = 0) OR (y = 0)
END {Euclid}.

{END:  CS217:EUCLIDR.TEXT  }