Answer 4

Euclid's algorithm is one possible solution. It assumes that x <= y.

  unsigned int gcd (unsigned int x, unsigned int y)
  {
    unsigned int r = y % x;
    return r ? gcd (r, x) : x;
  }
  

The function performs a division with remainder, and if the remainder isn't zero then it calls another version of itself (which performs a division with remainder, and if the remainder isn't zero it calls another version of itself, et cetera.)

It works because if x divides y, then x is the GCD of x and y. If x doesn't divide y exactly, then y = x×t + r. You can show that whatever the GCD of x and y is, it also divides r, so the algorithm is executed again on r and x.

How does the recursion eventually stop?

We start by plugging in two values x and y, with x less than y. The remainder, r, is guaranteed to be smaller than both x and y (why?) Now, the GCD function calls another version of the GCD function, but instead of plugging in x and y again, it plugs in two different values, the first of which is smaller than x and the second of which is no larger than y.

In other words, each time the function is called, the numbers plugged into it are smaller than they were last time. These are positive whole numbers, and therefore can't decrease in value forever. The lowest we can get is x=1 and y=2, and 1 divides evenly into 2. The program may stop before that, but it will certainly have to stop eventually.

Here's a nonrecursive implementation.

  unsigned int gcd (unsigned int x, unsigned int y)
  {
    unsigned int r;

    while (r = y % x) {
      y = x;
      x = r;
    }
    return x;
  }
  

Contributor: Naveen PN

Published: November-2002