GCD Recursion in Python

   July 14, 2022
GCD Recursion in Python

Introduction

Hello friends and welcome to our website violet-cat-415996.hostingersite.com. In this tutorial, we are going to learn a simple program of GCD Recursion in Python. Until now, we have covered various topics of python from basic to advanced projects, and have shared a number of tutorials for that. Here we going to study the different ways to find GCD recursion in Python and get a basic idea of it.

What is GCD?

A GCD or Greatest Common Divisor of two integers or more integers is the largest positive integer that allows the dividing of both numbers without leaving any remainder.

Example: To find GCD of 54 and 24

All divisors of 54 are 1, 2, 3, 6, 9, 18, 27, 54

All divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24

Common divisors of 54 and 24 are 1, 2, 3, 6

gcd(54,24) is 6 i.e. greatest common divisor of 54 and 24 is 6.

GCD Recursion method

A GCD recursion method is a method of tail recursion. A tail recursion means, the last thing a method does is to call itself. The tail recursion and the iteration in the program enable us to repeat a compound statement.

Let us understand the python program of GCD Recursion in detail

Python program for GCD of two numbers using Recursion

Method1 for GCD using Recursion in Python

#Define the function  gcsd
def  gcd(a,b):

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

#Takes the input values in a and b
a=int(input("Enter first number:"))
b=int(input("Enter second number:"))

#output of the gcd  function
output =gcd(a,b)
print("Greatest Common Divisor is: ")
print(output)

Explanation:

Let us understand the code of the Python Program of GCD Recursion line by line:

  1. We have defined a function gcd(a,b) in which we can take 2 parameters in a and b.
  2. We have defined the if block in which if the value of b==0 then the output is the value of a. else the function is recursively called with the arguments as the second number and the remainder, as the first number is divided by the second number.
  3. “a” and “b” are variables that take the input numbers.
  4. The “output” variable takes the output returned.
  5. The print function prints the statement and the output.

Outputs:

Case1:

Output1 of gcd recursion python
Output1 of GCD Recursion using Python

Case2:

Output2 of gcd code in python
Output2 of GCD Recursion using Python

Method2 for GCD Recursion Python

def gcd(a, b):
   if a == b:
      return a
   elif a < b:
      return gcd(b, a)
   else:
      return gcd(b, a - b)

#Defined the values of a and b
a = 20
b = 4
print(gcd(a, b))

Explanation:

  1. In the method, we have defined function gcd which takes  2 parameters a,b.
  2. Here we have used the if-else block where in the if block we check if a==b i.e if both a and b values are the same then it will return the value a, else if  a<b then it calls gcd(b, a) else when both the conditions become false it will recursively call the gcd(b,a-b) function till we get the output
  3. .Here we have defined the values of a and b as 20 and 4 respectively.
  4. Print(gcd(a,b)) prints the output of the function.

Output

Output3 of gcd python program
Output3 of GCD Recursion using Python

Hence, we have discussed two methods to calculate GCD Recursion using Python programming language.

For more articles on python keep visiting our site.

Thank you for reading this article.

Buy Python Handwritten Notes

Also Read:

Share:

Author: Ayush Purawr