Eulclid's Algorithm : Python code returns None at the end of recursion

Question

I am trying to implement Euclid's algorithm for computing the greatest common divisor using recursion. Below is the code for the same.

def euclid(a,b):
    if a>b:
        r=a%b
        if (r == 0):
            return b
        else:
            a=b
            b=r
            euclid(a,b)

print(euclid(20,4)) # Returns 4
print(euclid(20,8)) # Returns None

For the first data set, I get the correct result. But for euclid(20,8) I get a return of None.

While checking in the debugger, I did see the return value of b become 4 but then for some reason, my code jumps to euclid(a,b) and returns None.

The major takeaway here would be to understand why the code does not return 4 but jumps to the euclid(a,b) and return None.

Please refrain from giving alternative code solutions but you are very much encouraged to point out the reason for the current behaviour of the code.

Answer 1

You don't actually return anything in the else path so it just assumes you know best and returns None for you.

The only reason you get 4 for print(euclid(20,4)) is because 4 is a factor of 20 so never uses the else path. Instead it returns b immediately. For anything else, the thing returned from the first recursive call to euclid() will always be None (even if a lower call to that function returns something, you throw it away when returning from the first call).

You need return euclid(a,b) rather than just euclid(a,b).

---

As an aside (this isn't necessary to answer your specific question but it goes a long way toward improving the implementation of the code), I'm not a big fan of the if something then return else … construct since the else is totally superfluous (if it didn't return, the else bit is automatic).

Additionally, you don't need to assign variables when you can just change what gets passed to the next recursive level.

Taking both those into account (and simplifying quite a bit), you can do something like:

def euclid(a, b):
    if b == 0: return a
    return euclid(b, a % b)

Answer 2

The reason for that code to return None at some point is that in your control flow you eventually end up in a situation where there is no return statement, e.g. for a <= b in your first if or when r != 0 in your second if. The default behavior of Python in that case is to return None, as you seems to have discovered the hard way.

def euclid(a,b):
    if a>b:
        r=a%b
        if (r == 0):
            return b
        else: # <--- no `return` in this branch!
            a=b
            b=r
            euclid(a,b)
    # else:  # <--- no `return` in this branch!
    #     ...   

---

Here is an updated version of your code, that addresses that and also a number of other issues:

• the name of the function should be meaningful: Euclid is kind of popular and there is a bunch of things named after him, better specify that you actually want to compute the greatest common divisor (GCD)
• the first if is not really needed, as it is taken care of by the subsequent code: computing r and the recursive call will take care of swapping a and b if a < b, and if a == b then r == 0, so you b is being returned directly
• a = b and b = r are useless, do not use them, just have your recursive call use b and r directly
• the second if can be written more clearly in one line

def gcd_euclid_recursive(a, b):
    r = a % b
    return gcd_euclid_recursive(b, r) if r else b


gcd_euclid_recursive(120, 72)
# 24

gcd_euclid_recursive(64, 120)
# 8

Answer 3

Your code has an indentation error and one path is missing in your code(r!=0). It should be

def euclid(a,b):
    if a>=b:
        r=a%b
        if (r == 0):
            return b
        return euclid(b, r)
    else:
        return euclid(b, a)