Understanding the implementation of Euclid's Algorithm for GCF in Python

Question

Euclid's Algorithm for GCF of two numbers is: GCF(a, b)=GCF(b, a mod b). I have seen this implemented in Python as follows:

def gcf(a, b):
    return b and gcf(b, a%b) or a

I don't understand how to parse this function or specifically how boolean logic is applied to integers. For example, gcf(42, 56) = 14. When I walk through it, I see that eventually the recursive part returns zero. I follow that 0 or n == n and 0 and n == 0. However, once I have a pair of non-zero integers being compared with and/or logic, I don't understand what happens and why.

Can someone walk me through this function?

Answer 1

Python boolean operators 'or' and 'and' don't return boolean values. They return one of the values they are comparing.

0 or n - returns n

0 and n - returns 0

a and b or c is just a trick to implement the (a ? b : c) syntax in C.

Read section 4.6 of Dive into Python for a great description of python's boolean operations and this trick.

Answer 2

In your case, the call stack will look like this:

gcf(42, 56)
gcf(56, 42) // since b was non-zero, will recurse and pass 42 % 56 (=42) as second arg
gcf(42, 14) // since b was non-zero, will recurse and pass 56 % 42 (=14) as second arg
gcf(14, 0) // since b was non-zero, will recurse and pass 42 % 14 (=0) as second arg
return a // since b was zero, will just return a (14)

This will pop all the way to the top. In python, the and will return the number and not a boolean, which is why popping up returns the result and not a 1/true.

Answer 3

However, once I have a pair of non-zero integers being compared with and/or logic, I don't understand what happens and why.

What happens is that the first value that affects the result is returned.

x or y -> evaluates to x whenever code in an if x: block would run, and otherwise evaluates to y.

x and y -> evaluates to x whenever code in an if x: block would not run, and otherwise evaluates to y.

Why that happens is because GvR said so. It might, possibly, have been precisely to make this trick work, back before the x if C else y construct was added to the language.

But, you know... you could have just tested it for yourself. That's what the REPL is for :)

Answer 4

If b is not equal to zero then the result is gcf(b, a%b) (recurse). If b is equal to zero then the result is a.