Euclidean Algorithm - The Recursive Way

Last week I posted about various forms of the Euclidean Algorithm. This week, what with recursion being a topic in CSC148, I thought I'll implement the subtraction method using recursion (division next week).

First, just to quickly restate, Euclidean Algorithm tells us that, if x > y then gcd(x, y) = gcd(x - y, y). In class we implemented this using an iterative method (involving loops, etc.). Here is how we could implement it recursively:

def gcd(x, y):
    if x == 0:
        return y
    elif y = 0:
        return x
    elif x > y:
        return gcd(x - y, y)
    elif y > x:
        return gcd(x, y - x)

Quick explanation of code: You can probably guess why the first two if's are there; they're there because gcd(x, 0) = x and gcd(0, y) = y. But what about the last two if statements? Well we know if x > y then gcd(x, y) = gcd(x - y, y), thus we can evaluate and return this simplified expression. In the process of evaluating it, it may have to evaluate a further simplified gcd. It will keep doing this until one of the expressions contains a parameter that equals 0; when the function can return a value to the previous function.

Okay, that last paragraph was a mouthful; hopefully everyone understood what I was trying to say. If not, feel free to ask in the comments!