Trying to figure out recursive algorithm to find greatest common divisor of two integers

[Greg Stevens]

I have not searched the forums on this because I want to try to work out as much of this on my own as I can.
I know how to solve this with with a loop. If the the larger integer can be divided by the smaller integer with a remainder
of 0, then the smaller integer is the greatest common divisor. Otherwise, iterate from (smaller - 1) down to 1 and check
for divisibility for both larger and smaller integer.

I know I should be thinking in terms of a base case and a simplification of the original problem, but I don't see it.

Any small hint?

[Greg Stevens]

I remember now that the solution is the Euclidean algorithm. Never mind. I will try some other recursive problem.

[Rob Spoor]

Here's the general non-recursive algorithm:

public static int gcd(int a, int b)
{
    int t;
    while (b != 0)
    {
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

Now try and convert that into a recursive call. You already have the finished condition: max % mid == 0. Another possibility is a == b.

To make it easier, the first step can be to make sure that a is larger than b:

if (a < b)
{
    return gcd(b, a);
}
// other code

Hint: the actual Euclidian algorithm described here already is a recursive call, with the finished condition being b == 0.