CODEWITHSUNDEEP
pythonrecursion
sam007
sam007

Reputation: 83

Maximum recursion, GCD(greatest common divisor)

I wrote a program to find gcd using python.

def gcd(a,b):
    r=a%b
    if r==0:
        return a
    elif r==1:
        return 1
    else:
        gcd(a,b)==gcd(b,r)
        return gcd(b,r)

Whenever I call the function it shows the message "Max. recursion exceeded." Please help I know it can be done using looping but I want to specifically do it by using recursion method. And bear with me. I am a learner!

Upvotes: 1

Views: 8704

Answers (5)

Casey lin
Casey lin

Reputation: 1

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

Upvotes: 0

r3mainer
r3mainer

Reputation: 24567

If you're trying to calculate the GCD of very large numbers (e.g., when searching for common factors in RSA moduli), you might be better off avoiding recursion altogether and using an iterative function instead. For example:

def gcd(a,b):
    while a:
        a,b = b%a,a
    return b

Upvotes: 3

Altynbai
Altynbai

Reputation: 1

This is how I did it

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

Upvotes: 0

Paulo Bu
Paulo Bu

Reputation: 29794

This statement is unnecessary and it's the one making the recursion endless: gcd(a,b)==gcd(b,r) because it's calling gcd(a,b) again and again. Just remove it:

def gcd(a,b):
    r=a%b
    if r==0:
        return a
    elif r==1:
        return 1
    return gcd(b,r)

Note: By the way, you got the formula wrong, you should return b on the if clause since you're dividing a/b when calculating the modulo.

def gcd(a,b):
    r=a%b
    if r==0:
        return b
    elif r==1:
        return 1
    return gcd(b,r)

>>>gcd(10,4)
2

Upvotes: 3

Sebastian Paaske Tørholm
Sebastian Paaske Tørholm

Reputation: 50868

gcd(a,b)==gcd(b,r) doesn't do what you expect it to do.

It doesn't mean "define gcd(a,b) to be equal to gcd(b,r)".

Instead, gcd(a,b)==gcd(b,r) means:

  • Compute gcd(a,b)
  • Compute gcd(b,r)
  • Compare the two results and see if they're equal.

Since you're asking to compute gcd(a, b) in order to compute gcd(a, b), you'll get an endless recursion.

Instead, you want the return gcd(b, r) at that point. I.e.:

def gcd(a,b):
    r=a%b
    if r==0:
        return a
    elif r==1:
        return 1
    else:
        return gcd(b,r)

Upvotes: 1

Related Questions