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.