13
\$\begingroup\$

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.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> 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.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    if b > 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?

\$\endgroup\$
15
\$\begingroup\$

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 > 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.

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

    if a % b == 0:
        return b

    return gcd(b, a % b)        
\$\endgroup\$
  • \$\begingroup\$ So you are making sure first argumentt is bigger than second \$\endgroup\$ – overexchange Jul 2 '15 at 3:11
  • \$\begingroup\$ Yes, and note I also now removed the else. It was redundant \$\endgroup\$ – rolfl Jul 2 '15 at 3:15
  • 11
    \$\begingroup\$ If b > a then a % b = a, and the first recursive call will be equivalent to swapping the input arguments, so you don't really need that first branch at all. Also, if you let the recursion go one level deeper, you don't need to compute a % b twice, or store it in a temp variable, but can simply do: def gcd(a, b): return gcd(b, a % b) if b else a. \$\endgroup\$ – Jaime Jul 2 '15 at 4:48
  • \$\begingroup\$ FWIW, for some intuition, try def gcd(a, b): return print(a,b) or (gcd(b, a % b) if b else a). \$\endgroup\$ – A-B-B Nov 1 '16 at 23:10
12
\$\begingroup\$

This is slightly irrelevent but you can improve your code quite easily by removing recursion.

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

Some might argue that this reduces readibility but with a name gcd, I find it hard to believe, especially considering the fact that Euclidean algorithm is quite popular.

\$\endgroup\$
  • 4
    \$\begingroup\$ Since Python doesn't optimize tail recursion (stackoverflow.com/q/13591970/2073469), this will also be be way more efficient, both time and space wise. \$\endgroup\$ – jacwah Dec 3 '16 at 16:12
  • \$\begingroup\$ Recursion is considered cool and elegant from a mathematical standpoint but the performance penalty is often ignored. \$\endgroup\$ – ChuckCottrill Nov 6 '17 at 0:58
3
\$\begingroup\$

Starting from Python version 3.5, we can use math.gcd(a, b) function from math module. So, instead of creating nested if we can use this function.

From documentation:

math.gcd(a, b)
Return the greatest common divisor of the integers a and b. If either a or b is nonzero, then the value of gcd(a, b) is the largest positive integer that divides both a and b. gcd(0, 0) returns 0.

math.gcd(a, b) is implemented as:

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a
\$\endgroup\$
  • \$\begingroup\$ This is new answer to the old question, so please post a comment to suggest improvement. \$\endgroup\$ – Ram Chandra Giri Oct 9 '17 at 12:39

protected by Jamal Sep 4 '17 at 22:31

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.