Recursive function to find out GCD

GCD is known as the greatest common divisor. It is the largest number that is able to divide both numbers. The process of finding the greatest number is as follows

  • Divide first number by the second number. if the second number is able to divide it completely then the first number is GCD of both
  • If the second number is not able to divide completely then the divider becomes number for the next step and the remainder becomes the divider.
  • Continue this process unless divider divides the number completely

Python recursion Function to find out GCD

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

if __name__ == "__main__":
    a = int(input('Enter first number '))
    b = int(input('Enter second number '))
    result = gcd(a, b)
    print('GCD of {} and {} is {}'.format(a, b, result))

The same program can be written using iterative methods also.

GCD using Looping method

#   program to find out GCD of two number using iterative method
#   made by     : rakeseh kumar


a = int(input('Enter any number'))
b = int(input('Enter another number'))

""" if(a > b):
    number = a
    divider = b
else:
    number = b
    divider = a """

rem = a % b

while(rem != 0):
    a = b
    b = rem
    rem = a % b

print('Your GCD is :', b)
Here is the output of the above program
rakesh@folio MINGW64 /e/python (master)
$ python -u "e:\python\Loops\gcd_two.py"
Enter any number8
Enter another number24
Your GCD is : 8

If you have any questions related to this Recursive Python function to find out GCD. Please send us your queries via email.

Related Posts

If you like CBSEToaday and would like to contribute, you can also write an article using submit article or mail your article to contribute@cbsetoday.com See your article appearing on the cbsetoday.com main page and help other students/teachers.