Python GCD implementations
Your implementation is as efficient as it can be in python. Because python is an interpreted language, every statement that is executed takes a long time compared to something like c.

At the bottom of this answer is an altered version of your code that times 1000 evaluations of both of the functions. It also records the total amount of time spent evaluating the first three lines of the binary algorithm.

Below is the output of the code:

Euler:             0.0010025501251220703
Binary1:           0.2012491226196289
First three lines: 0.04787778854370117


The amount of time spent checking for a==b, a==0, and b==0 takes longer than the entire Euler algorithm. It should be noted that the binary algorithm is only supposed to be faster when dealing with "regular" arithmetic. From the Wikipedia page on the binary gcd algorithm:

"For arbitrary-precision arithmetic, neither the Euclidean algorithm nor the binary GCD algorithm are fastest, as they both take time that is a quadratic function of the number of input digits."

first_three_lines = 0

def gcd_euclid_recursive(a, b):
    if b == 0: return a
    return gcd_euclid_recursive(b, a % b)

def gcd_binary_recursive(a, b):
    global first_three_lines
    t = time()
    if a == b: return a
    if a == 0: return b
    if b == 0: return a
    first_three_lines += time() - t

    if a &amp; 1 == 0: # a is even
        if b &amp; 1 == 1: # b is odd
            return gcd_binary_recursive(a &gt;&gt; 1, b)
        else: # both a and b are even
            return gcd_binary_recursive(a &gt;&gt; 1, b &gt;&gt; 1) &lt;&lt; 1

    if b &amp; 1 == 0: # a is odd and b is even
        return gcd_binary_recursive(a, b &gt;&gt; 1)

    if (a &gt; b):
        return gcd_binary_recursive((a-b) &gt;&gt; 1, b)
    return gcd_binary_recursive((b-a) &gt;&gt; 1, a)

a = 5**100 - 1
b = 5**120 - 1


from time import time
euler_time = 0
for i in range(1000):
    t = time()
    x = gcd_euclid_recursive(a,b)
    euler_time += time() - t

bin_time = 0
for i in range(1000):
    t = time()
    x = gcd_binary_recursive(a,b)
    bin_time += time() - t

print("Euler:            ",euler_time)
print("Binary1:          ",bin_time)
print("First three lines:",first_three_lines)
```