Can anyone help explain to me how this code works? I am trying to understand how recursion works and how to write it.
def gcdRecur(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
if b == 0:
return a
else:
return gcdRecur(b,a % b)
obj = gcdRecur(9,12)
print (obj)
This is an implementation of the Euclidean algorithm.
The basic principle is that the greatest common factor of a and b (where b < a, which it will be after a step at most) is also the greatest common factor of b and the remainder when you divide a by b.
By repeatedly applying this step, you get down to a case where eventually the remainder is 0 (because it can be shown the remainder keeps getting smaller) and then the gcf is the other number. So in your example of 9 and 12 it goes to 12 and 9, then 9 and 3, then 3 and 0 and returns 3 which is right.
The way the function works is through recursion, which means it calls itself.