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