GCD using Euclid algorithm Below is the problem taken from here.


  Question 10: GCD*
  
  The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of a and b is one of the following:
  
  the smaller value if it evenly divides the larger value, OR
  the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value
  In other words, if a is greater than b and a is not divisible by b, then
  
  gcd(a, b) == gcd(b, a % b)
  
  Write the gcd function recursively using Euclid's algorithm.

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    &gt;&gt;&gt; gcd(34, 19)
    1
    &gt;&gt;&gt; gcd(39, 91)
    13
    &gt;&gt;&gt; gcd(20, 30)
    10
    &gt;&gt;&gt; gcd(40, 40)
    40
    """
    "*** YOUR CODE HERE ***"



Solution:

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    &gt;&gt;&gt; gcd(34, 19)
    1
    &gt;&gt;&gt; gcd(39, 91)
    13
    &gt;&gt;&gt; gcd(20, 30)
    10
    &gt;&gt;&gt; gcd(40, 40)
    40
    """
    if b &gt; a:
        if b % a == 0:
            return a
        else:
            return gcd(b % a, a)
    else:
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)        


How can I improve this nested if block?
One of the nice things with recursion is that you can use it for argument handling.

Where you have a conditional to handle the b &gt; a condition, you could instead use recursion.....

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    &gt;&gt;&gt; gcd(34, 19)
    1
    &gt;&gt;&gt; gcd(39, 91)
    13
    &gt;&gt;&gt; gcd(20, 30)
    10
    &gt;&gt;&gt; gcd(40, 40)
    40
    """
    if b &gt; a:
        return gcd(b, a)

    if a % b == 0:
        return b

    return gcd(b, a % b)