Python Recursive Call

1
votes

I want to run This code But it gives This Error: if n == 0: RecursionError: maximum recursion depth exceeded in comparison

    def gcd(n, m):
    if n == 0:
        return m
    else:
        return gcd(n, m % n)


print(gcd(10, 50))

Anyone Knows Why ?

2
pythonrecursion
you never decrease n (the first argument); therefore the condition n == 0 will never hold. - hiro protagonist
You're never changing the value of n... When would it be 0? - OneCricketeer
Thanks! I must change the place of m and n in def. - Mostafa Orooji

2 Answers

0
votes

When you do the second return you are actually saying n = n and m = m % n for the next iteration. You are effectively changing the value of m but never the one of n so it never gets to 0. Your function is never getting to the exit condition of n = 0.

-1
votes

To calculate GCD you need to account for both numbers. By checking only n for termination condition and yet mutating only m, you keep n the same indefinitely in all your recursions, never reaching the termination condition.

You should use the lesser of the two numbers as the divider and pass the remainder to the other number in the next recursion.

def gcd(n, m):
    if n == 0:
        return m
    if m == 0:
        return n
    if n > m:
        return gcd(n % m, m)
    return gcd(n, m % n)

print(gcd(10, 50))