CODEWITHSUNDEEP
pythonrecursion
Daniel McCrevan
Daniel McCrevan

Reputation: 179

Confused on recursive function

I don't understand the difference between these two functions, why does the one that returns the function work but the other doesn't?

The function returns the greatest common denominator between x and y assuming x > y

Non-working function:

def gcd(x, y):
    z = x % y
    if z == 0:
        return y
    else:
        gcd(y, z)

Working function:

def gcd(x, y):
    z = x % y
    if z == 0:
        return y
    else:
        return gcd(y, z)

Upvotes: 1

Views: 121

Answers (1)

Patrick Haugh
Patrick Haugh

Reputation: 61052

Every function in python returns something. In fact, you can put a return None statement at the end of every function in python without changing anything about how those functions work. So your first function can be written

def gcd(x, y):
    z = x % y
    if z == 0:
        return y
    else:
        gcd(y, z)
    return None

So when I call gcd(28, 14) I get None. When you return the recursive call to gcd, the code is equivalent to

def gcd(x, y):
    z = x % y
    if z == 0:
        return y
    else:
        return gcd(y, z)
    return None

so we either return 0 or whatever gcd(y, z) is, but never None, because the code never gets that far.

Upvotes: 4

Related Questions